Pagini recente » Cod sursa (job #1261134) | Cod sursa (job #684183) | Cod sursa (job #754226) | Cod sursa (job #561561) | Cod sursa (job #1518703)
#include <stdio.h>
#define MAXN 16000
#define MAXM 100000
#define CD 2000000000
#define MOD 666013
#define BUFF (1 << 20)
FILE *in;
unsigned int xnorm[MAXN + 2 * MAXM];
unsigned int xp[MAXN + 1], yp[MAXN + 1], x1d[2 * MAXM + 1], x2d[2 * MAXM + 1], yd[2 * MAXM + 1], dt[2 * MAXM + 1];
int tip[MAXN + 2 * MAXM + 1], point[MAXN + 2 * MAXM + 1];
int rez[MAXM + 1];
int nr = 1;
int ult[MOD], hash[MAXN + 2 * MAXM + 1], next[MAXN + 2 * MAXM + 1];
int aib[MAXN + 2 * MAXM + 1];
char ssin[BUFF];
int pin = BUFF;
inline char cif(char ch){
if(ch >= '0' && ch <= '9')
return 1;
return 0;
}
inline char getcharr(){
if(pin == BUFF){
fread(ssin, 1, BUFF, in);
pin = 0;
}
pin++;
return ssin[pin - 1];
}
inline long long getnumm(){
char ch = getcharr();
long long rez = 0;
int m;
while(!cif(ch) && ch != '-')
ch = getcharr();
if(ch == '-'){
m = -1;
ch = getcharr();
}
else
m = 1;
while(cif(ch)){
rez *= 10;
rez += ch - '0';
ch = getcharr();
}
return rez * m;
}
inline char cmp(int point, unsigned int py, int pt){
unsigned int cy;
int ct;
if(point < 0){
cy = yd[-point];
ct = 1;
}
else{
cy = yp[point];
ct = -1;
}
if(cy > py)
return 2;
else if(cy < py)
return 0;
else{
if(ct < pt)
return 0;
else if(ct > pt)
return 2;
else
return 1;
}
}
void qs(int st, int dr){
int i = st, j = dr, mid = (st + dr) / 2, pt, aux;
unsigned int py;
if(point[mid] < 0){
py = yd[-point[mid]];
pt = 1;
}
else{
py = yp[point[mid]];
pt = -1;
}
while(i <= j){
while(cmp(point[i], py, pt) == 0)
i++;
while(cmp(point[j], py, pt) == 2)
j--;
if(i <= j){
aux = point[i]; point[i] = point[j]; point[j] = aux;
i++; j--;
}
}
if(st < j)
qs(st, j);
if(i < dr)
qs(i, dr);
}
void qs2(int st, int dr){
int i = st, j = dr, piv = xnorm[(st + dr) / 2];
unsigned int aux;
while(i <= j){
while(xnorm[i] < piv)
i++;
while(xnorm[j] > piv)
j--;
if(i <= j){
aux = xnorm[i]; xnorm[i] = xnorm[j]; xnorm[j] = aux;
i++; j--;
}
}
if(st < j)
qs2(st, j);
if(i < dr)
qs2(i, dr);
}
inline void addhash(unsigned int y){
int k = y % MOD, poz;
poz = ult[k];
while(poz != 0 && hash[poz] != y)
poz = next[poz];
if(poz == 0){
hash[nr] = y;
next[nr] = ult[k];
ult[k] = nr;
nr++;
}
}
inline int care(unsigned int y){
unsigned int k = y % MOD, poz;
poz = ult[k];
while(poz != 0 && hash[poz] != y)
poz = next[poz];
return poz;
}
inline int ultb(int x){
return x & (-x);
}
int suma(int x){
if(x == 0)
return aib[0];
return aib[x] + suma(x - ultb(x));
}
void addaib(int x){
if(x <= nr){
aib[x]++;
addaib(x + ultb(x));
}
}
inline void calc(int n, int m){
int i;
for(i = 1; i <= n + 2 * m; i++){
if(point[i] < 0)
rez[dt[-point[i]]] += tip[-point[i] + n] * (suma(care(x2d[-point[i]])) - suma(care(x1d[-point[i]])));
else
addaib(care(xp[point[i]]));
}
}
int main(){
in = fopen("zoo.in", "r");
int n, m, i, a, b, c, d;
n = (int)getnumm();
for(i = 1; i <= n; i++){
a = (int)getnumm(); b = (int)getnumm();
xnorm[i] = a + CD + 1;
xp[i] = a + CD + 1;
yp[i] = b + CD + 1;
point[i] = i;
tip[i] = -2;
}
m = (int)getnumm();
int dr = 1;
for(i = 1; i <= m; i++){
a = (int)getnumm(); b = (int)getnumm();
c = (int)getnumm(); d = (int)getnumm();
xnorm[dr + n] = a + CD;
x1d[dr] = a + CD; x2d[dr] = c + CD + 1;
yd[dr] = b + CD;
dt[dr] = i;
tip[dr + n] = -1;
point[dr + n] = -dr;
dr++;
xnorm[dr + n] = c + CD + 1;
x1d[dr] = a + CD; x2d[dr] = c + CD + 1;
yd[dr] = d + CD + 1;
dt[dr] = i;
tip[dr + n] = 1;
point[dr + n] = -dr;
dr++;
}
fclose(in);
qs(1, n + 2 * m);
qs2(1, n + 2 * m);
for(i = 1; i <= n + 2 * m; i++)
addhash(xnorm[i]);
nr--;
calc(n, m);
FILE *out = fopen("zoo.out", "w");
for(i = 1; i <= m; i++)
fprintf(out, "%d\n", rez[i]);
fclose(out);
return 0;
}