Pagini recente » Borderou de evaluare (job #85728) | Borderou de evaluare (job #3356568) | Borderou de evaluare (job #2584585) | Borderou de evaluare (job #3326535) | Cod sursa (job #3328167)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ograzi.in");
ofstream fout("ograzi.out");
const int MAXC = 1000000;
struct Operatie {
int x, y1, y2;
Operatie() {}
Operatie(int _x, int _y1, int _y2): x(_x), y1(_y1), y2(_y2) {}
};
int n, m, w, h, i, j, rasp;
vector<Operatie> op;
int aib[MAXC + 2];
static inline void Update(int poz, int val) {
poz++;
while(poz <= MAXC) {
aib[poz] += val;
poz += (poz & -poz);
}
}
static inline int Query(int poz) {
int sum = 0;
poz++;
while(poz >= 1) {
sum += aib[poz];
poz -= (poz & -poz);
}
return sum;
}
static inline bool Cmp(Operatie a, Operatie b) {
if(a.x != b.x) return a.x < b.x;
return a.y2 > b.y2;
}
int main() {
ios_base::sync_with_stdio(false);
fin.tie(nullptr);
fout.tie(nullptr);
fin >> n >> m >> w >> h;
for(i = 1; i <= n; i++) {
int x, y;
fin >> x >> y;
op.push_back(Operatie(x, y - 1, -1));
op.push_back(Operatie(x, y + h, 1));
op.push_back(Operatie(x + w, y - 1, -1));
op.push_back(Operatie(x + w, y + h, 1));
}
for(i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
op.push_back(Operatie(x, y, -2));
}
sort(op.begin(), op.end(), Cmp);
for(Operatie cur : op) {
//cout << cur.x << " " << cur.y1 << " " << cur.y2 << "\n";
if(cur.y2 == -2) rasp += Query(cur.y1) - Query(cur.y1 - 1);
else Update(cur.y1, cur.y2);
}
fout << rasp;
return 0;
}