Cod sursa(job #1561646)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 4 ianuarie 2016 12:58:28
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream in("ograzi.in");
ofstream out("ograzi.out");

const int MAX_N = 50000;
const int MAX_M = 100000;
const int MAX_H = 1000000;

struct Event {
    char type;
    int x;
    int y;
};

int eCount;
Event E[1 + 4 * MAX_N + MAX_M];
int AIB[1 + MAX_H];

int getLSB(int X) {
    return X & (-X);
}

void update(int pos, int val) {
    int i;
    for(i = pos; i <= MAX_H; i += getLSB(i)) {
        AIB[i] += val;
    }
}

int query(int pos) {
    int i, ans = 0;
    for(i = pos; i; i -= getLSB(i)) {
        ans += AIB[i];
    }
    return ans;
}

bool eventSort(Event A, Event B) {
    if(A.x == B.x) return A.type < B.type;
    return A.x < B.x;
}

int main() {
    int n, m, w, h, i, x, y, t, ans = 0;

    in >> n >> m >> w >> h;
    for(i = 1; i <= n; i++) {
        in >> x >> y;
        E[++eCount] = Event{0, x, y};
        E[++eCount] = Event{1, x, y + h};
        E[++eCount] = Event{1, x + w, y};
        E[++eCount] = Event{0, x + w, y + h};
    }
    for(i = 1; i <= m; i++) {
        in >> x >> y;
        E[++eCount] = Event{2, x, y};
    }

    sort(E+1, E+eCount+1, eventSort);
    for(i = 1; i <= eCount; i++) {
        x = E[i].x;
        y = E[i].y;

        if(E[i].type == 0) {
            update(y, 1);
        }
        else if(E[i].type == 1) {
            update(y, -1);
        }
        else {
            ans += query(y);
        }
    }

    out << ans << '\n';

    return 0;
}