Pagini recente » Cod sursa (job #2736481) | Cod sursa (job #1606297) | Cod sursa (job #2757318) | Cod sursa (job #2671111) | Cod sursa (job #2505112)
#include <bits/stdc++.h>
FILE *in = fopen("ograzi.in", "r"), *out = fopen("ograzi.out", "w") ;
const int MV = 1e6 ;
struct event {
int ordonata, abscisa ;
int type ;
void fix(int a, int b, int c) {
this ->ordonata = a ;
this ->abscisa = b ;
this ->type = c ;
}
bool operator <(const event &aux) const {
if (this ->ordonata == aux.ordonata) {
return this ->type > aux.type ;
} return this ->ordonata > aux.ordonata ;
}
};
int width, height ;
int goodSheeps ;
std::priority_queue<event> events ;
int BIT[MV + 1] ;
void update(int poz, int val) {
for (int i = poz ; i <= MV ; i += (i & -i)) {
BIT[i] += val ;
}
}
int query(int poz) {
int ret(0) ;
for (int i = poz ; i > 0 ; i -= (i & -i)) {
ret += BIT[i] ;
}
return ret ;
}
void eval(event currentEvent) {
if (currentEvent.type == 1) {
int rectangles = query(currentEvent.abscisa) - query(currentEvent.abscisa - height - 1) ;
if (rectangles > 0) {
goodSheeps ++ ;
}
return ;
}
if (currentEvent.type == 0) {
update(currentEvent.abscisa, 1) ;
event new_event ;
new_event.fix(currentEvent.ordonata + width + 1, currentEvent.abscisa, 2) ;
events.push(new_event) ;
return ;
}
if (currentEvent.type == 2) {
update(currentEvent.abscisa, -1) ;
return ;
}
}
void runOX() {
while (events.size() > 0) {
event currentEvent = events.top() ;
events.pop() ;
eval(currentEvent) ;
}
}
int main() {
int n, m ;
fscanf(in, "%d %d %d %d", &n, &m, &width, &height) ;
event new_event ;
int ord, absc ;
for (int i = 1 ; i <= n ; ++ i) {
fscanf(in, "%d %d", &ord, &absc) ;
new_event.fix(ord, absc, 0) ;
events.push(new_event) ;
}
for (int i = 1 ; i <= m ; ++ i) {
fscanf(in, "%d %d", &ord, &absc) ;
new_event.fix(ord, absc, 1) ;
events.push(new_event) ;
}
runOX() ;
fprintf(out, "%d", goodSheeps) ;
}