Pagini recente » Cod sursa (job #1850734) | Cod sursa (job #3245178) | Cod sursa (job #3210778) | Cod sursa (job #3249159) | Cod sursa (job #2704655)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin( "zoo.in" );
ofstream fout( "zoo.out" );
using namespace std;
const int Max = 250000;
struct event {
int x, y, type, ind, nq;
} q[Max];
int tree[4 * Max];
inline int left( int node ) {
return node << 1;
}
inline int right( int node ) {
return (node << 1) | 1;
}
int ux;
void update( int node, int l, int r ) {
if ( l == r ) {
++tree[node];
return;
}
int mid = (l + r) / 2;
if ( ux <= mid ) {
update( left( node ), l, mid );
} else {
update( right( node ), mid + 1, r );
}
tree[node] = tree[left( node )] + tree[right( node )];
}
int qa, qb;
int query( int node, int l, int r ) {
int x = 0, y = 0;
if ( qa <= l && r <= qb ) {
return tree[node];
}
int mid = (l + r) / 2;
if ( qa <= mid ) {
x = query( left( node ), l, mid );
}
if ( qb > mid ) {
y = query( right( node ), mid + 1, r );
}
return x + y;
}
struct cmpx {
bool operator () ( const event &a, const event &b ) {
return (a.x < b.x) || (a.x == b.x && a.type < b.type);
}
};
struct cmpy {
bool operator () ( const event &a, const event &b ) {
return a.y < b.y;
}
};
event nx[Max], ny[Max];
int res[Max];
int _y1[Max], _y2[Max];
int main() {
int n, m, nev;
fin >> n;
nev = 0;
for ( int i = 0; i < n; ++i ) {
fin >> q[nev].x >> q[nev].y;
q[nev].type = 0;
q[nev].ind = nev;
nx[nev] = ny[nev] = q[nev];
++nev;
}
fin >> m;
for ( int i = 0; i < m; ++i ) {
fin >> q[nev].x >> q[nev].y;
q[nev].type = -1;
q[nev].ind = nev;
++nev;
fin >> q[nev].x >> q[nev].y;
q[nev].type = 1;
q[nev].ind = nev;
q[nev - 1].nq = q[nev].nq = i;
nx[nev - 1] = ny[nev - 1] = q[nev - 1];
nx[nev] = ny[nev] = q[nev];
++nev;
}
sort( ny, ny + nev, cmpy() );
int cry = 1;
q[ny[0].ind].y = cry;
for ( int i = 1; i < nev; ++i ) {
if ( ny[i - 1].y == ny[i].y ) {
q[ny[i].ind].y = cry;
} else {
q[ny[i].ind].y = ++cry;
}
}
sort( q, q + nev, cmpx() );
for ( int i = 0; i < nev; ++i ) {
if ( q[i].type == -1 ) {
_y1[q[i].nq] = q[i].y;
}
if ( q[i].type == 1 ) {
_y2[q[i].nq] = q[i].y;
}
}
for ( int i = 0; i < nev; ++i ) {
if ( q[i].type == 0 ) {
ux = q[i].y;
update( 1, 1, cry );
} else if ( q[i].type == -1 ) {
qa = _y1[q[i].nq], qb = _y2[q[i].nq];
res[q[i].nq] = query( 1, 1, cry );
} else if ( q[i].type == 1 ) {
qa = _y1[q[i].nq], qb = _y2[q[i].nq];
res[q[i].nq] = query( 1, 1, cry ) - res[q[i].nq];
}
}
for ( int i = 0; i < m; ++i ) {
fout << res[i] << "\n";
}
fin.close();
fout.close();
return 0;
}