Pagini recente » Cod sursa (job #3220134) | Cod sursa (job #2777319) | Cod sursa (job #2617744) | Cod sursa (job #2405937) | Cod sursa (job #828609)
Cod sursa(job #828609)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define max_n 20000
#define max_m 120000
#define INF 2000000005
#define pb push_back
vector<int> El;
struct point {
int x,y,nr;
} Po[max_n],Ta[4*max_m];
bool mysort ( point a, point b ){
return a.y < b.y;
}
int Rez[4*max_m];
int n,m,i,j,rez;
int a,b,c,d,task;
int Aib[6*max_m];
void add ( int ind, int val ){
for ( ; ind < 6*max_m; ind+=(ind)&(-ind) )
Aib[ind]+=val;
}
int query ( int ind ){
int rez=0;
for ( ; ind; ind-=(ind)&(-ind) )
rez+=Aib[ind];
return rez;
}
int bs ( int val ){
int ind=(1<<19),rez=0;
for ( ; ind; ind>>=1 ){
if ( rez+ind < int(El.size()) ){
if ( El[ ind+rez ] <= val ){
rez+=ind;
}
}
}
return rez;
}
int main(){
freopen ("zoo.in","r",stdin);
freopen ("zoo.out","w",stdout);
scanf ("%d", &n );
for ( i=1; i<=n; i++ ){
scanf ("%d %d", &Po[i].x, &Po[i].y );
El.pb( Po[i].x );
El.pb( Po[i].y );
}
El.pb( INF );
El.pb( -INF );
Po[n+1].x=INF;
Po[n+1].y=INF;
scanf ("%d", &m );
for ( i=1; i<=m; i++ ){
scanf ("%d %d %d %d", &a, &b, &c, &d );
a--;
b--;
El.pb ( a );
El.pb ( b );
El.pb ( c );
El.pb ( d );
++task;
Ta[task].x = a;
Ta[task].y = b;
Ta[task].nr = task;
++task;
Ta[task].x = c;
Ta[task].y = d;
Ta[task].nr = task;
++task;
Ta[task].x = a;
Ta[task].y = d;
Ta[task].nr = task;
++task;
Ta[task].x = c;
Ta[task].y = b;
Ta[task].nr = task;
}
Ta[ task+1 ].x = INF;
Ta[ task+1 ].y = INF;
sort ( El.begin(), El.end() );
sort ( Ta+1, Ta+4*m+1, mysort );
sort ( Po+1, Po+n+1, mysort );
int ind1=1, ind2=1, act;
for ( ; ind1<=n || ind2<=4*m; ){
act = min ( Po[ind1].y , Ta[ind2].y );
if ( ind1 > n ){
act = Ta[ind2].y;
}
if ( ind2 > 4*m ){
act = Po[ind1].y;
}
// inseram punctele noi in AIB
while ( (ind1<=n) && ( Po[ind1].y == act ) ){
add ( bs ( Po[ind1].x ) , 1 );
ind1++;
}
// facem queryurile
while ( ( ind2<=4*m ) && ( Ta[ind2].y == act ) ){
Rez [ Ta[ind2].nr ] = query ( bs ( Ta[ind2].x ) );
ind2++;
}
}
for ( i=1; i<=m; i++ ){
rez=0;
rez += Rez[ (i-1)*4+1 ];
rez += Rez[ (i-1)*4+2 ];
rez -= Rez[ (i-1)*4+3 ];
rez -= Rez[ (i-1)*4+4 ];
printf("%d\n",rez);
}
return 0;
}