Pagini recente » Cod sursa (job #2372597) | Cod sursa (job #958004) | Monitorul de evaluare | Cod sursa (job #1966832) | Cod sursa (job #1896481)
#include <cstdio>
#include <algorithm>
const int MAX_N = 16000;
const int MAX_M = 100000;
const int MAX_E = 1001;
struct Valuta {
int tip, x, y1, y2;
int *upd;
} v[MAX_N + 2*MAX_M];
int rez[MAX_M];
bool cmp(Valuta a, Valuta b) {
return a.x < b.x || (a.x == b.x && a.tip < b.tip);
}
int aib[1+MAX_N+2*MAX_M];
inline int lastbit(int x) {
return x & (-x);
}
inline void upd(int p, int x) {
while(p <= MAX_E) {
aib[p] += x;
p += lastbit(p);
}
}
inline int querySt(int p) {
int rez = 0;
while(p > 0) {
rez += aib[p];
p -= lastbit(p);
}
return rez;
}
int query(int a, int b) {
return querySt(b) - querySt(a - 1);
}
bool cmp2(int *a, int *b) {
return *a < *b;
}
int *p[MAX_N + 4 * MAX_M];
void normalize(int n) {
int top = 0;
for(int i = 0; i < n; ++i)
if(v[i].tip == 0)
p[top++] = &v[i].y1;
else {
p[top++] = &v[i].y1;
p[top++] = &v[i].y2;
}
std::sort(p, p + top, cmp2);
int last = *p[0];
int j = 1;
for(int i = 0; i < top; ++i) {
if(*p[i] == last)
*p[i] = j;
else {
last = *p[i];
++j;
*p[i] = j;
}
}
}
int main() {
int n, x, top = 0, m, x2, y2, y;
FILE *fin = fopen("zoo.in", "r");
FILE *fout = fopen("zoo.out", "w");
fscanf(fin, "%d", &n);
for(int i = 1; i <= n; ++i) {
fscanf(fin, "%d%d", &x, &y);
v[top].x = x;
v[top].y1 = y;
top++;
}
fscanf(fin, "%d", &m);
for(int q = 0; q < m; ++q) {
fscanf(fin, "%d%d%d%d", &x, &y, &x2, &y2);
v[top].tip = 1;
v[top].x = x - 1;
v[top].y1 = y;
v[top].y2 = y2;
v[top].upd = &rez[q];
top++;
v[top].tip = 2;
v[top].x = x2;
v[top].y1 = y;
v[top].y2 = y2;
v[top].upd = &rez[q];
top++;
}
fclose(fin);
std::sort(v, v + top, cmp);
normalize(top);
for(int i = 0; i < top; ++i) {
if(v[i].tip == 0)
upd(v[i].y1, 1);
else {
int r = query(v[i].y1, v[i].y2);
if(v[i].tip == 1)
r = -r;
*v[i].upd += r;
}
}
for(int i = 0; i < m; ++i)
fprintf(fout, "%d\n", rez[i]);
fclose(fout);
return 0;
}