Pagini recente » Cod sursa (job #1015640) | Rating Daria Larisa (DariaLarisa) | Istoria paginii runda/pregatire_oji_11-12_ | Istoria paginii runda/pgleague | Cod sursa (job #2054688)
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
FILE *fi, *fout;
const int MAXBUF = (1 << 17);
char buf[MAXBUF];
int pbuf = MAXBUF;
inline char nextch() {
if(pbuf == MAXBUF) {
fread(buf, 1, MAXBUF, fi);
pbuf = 0;
}
return buf[pbuf++];
}
inline int getnr() {
char ch = nextch();
while(!isdigit(ch))
ch = nextch();
int nr = 0;
while(isdigit(ch)) {
nr = nr * 10 + ch - '0';
ch = nextch();
}
return nr;
}
const int MAXN = (int) 5e4;
const int MAXM = (int) 1e5;
struct Norm {
int val;
int pos;
bool operator <(const Norm &other) const {
if(val == other.val)
return pos < other.pos;
return val < other.val;
}
}x[2 * MAXM + MAXN + 1], y[2 * MAXM + MAXN];
int pts[MAXN + 1];
struct Rect {
int y1, y2;
}r[MAXM + 1];
int n, m;
inline int norm(Norm *v, int sz) {
std::sort(v + 1, v + sz + 1);
int val = 0;
v[0] = {-2, 0};
for(int i = 1; i <= sz; i++) {
if(v[i].val != v[i - 1].val)
val++;
if(v[i].pos <= m) {
pts[v[i].pos] = val;
}
else {
if(r[v[i].pos - m].y1 == 0)
r[v[i].pos - m].y1 = val;
else
r[v[i].pos - m].y2 = val;
}
}
return val;
}
int aib[MAXN + 2 * MAXM + 1];
inline void update(int p, int sz) {
for(int i = p; i <= sz; i += lsb(i))
aib[i]++;
}
inline int query(int p) {
int ans = 0;
for(int i = p; i > 0; i -= lsb(i))
ans += aib[i];
return ans;
}
bool ok[MAXM + 1];
int main() {
int w, h, i, j;
fi= fopen("ograzi.in" ,"r");
fout = fopen("ograzi.out" ,"w");
n = getnr();
m = getnr();
w = getnr();
h = getnr();
int sz = m;
for(i = 1; i <= n; i++) {
sz++;
x[sz].val = getnr();
y[sz].val = getnr();
x[sz].val--;
y[sz].val--;
x[sz].pos = y[sz].pos = m + i;
sz++;
x[sz].val = x[sz - 1].val + w + 1;
y[sz].val = y[sz - 1].val + h + 1;
x[sz].pos = y[sz].pos = m + i;
}
for(i = 1; i <= m; i++) {
x[i].val = getnr();
y[i].val = getnr();
x[i].pos = y[i].pos = i;
}
int maxy = norm(y, sz);
std::sort(x + 1, x + sz + 1);
int ans = 0;
for(i = 1; i <= sz; i++) {
if(x[i].pos <= m) {
update(pts[x[i].pos], maxy);
}
else {
int p = x[i].pos - m;
if(ok[p] == 0)
ans -= (query(r[p].y2) - query(r[p].y1));
else
ans += (query(r[p].y2) - query(r[p].y1));
ok[p] = 1;
}
}
fprintf(fout,"%d" ,ans);
fclose(fi);
fclose(fout);
return 0;
}