Cod sursa(job #2054688)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 2 noiembrie 2017 12:53:05
Problema Ograzi Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#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;
}