Cod sursa(job #2505112)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 6 decembrie 2019 10:38:43
Problema Ograzi Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.48 kb
#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) ;
}