Cod sursa(job #1947422)

Utilizator KusikaPasa Corneliu Kusika Data 30 martie 2017 22:37:46
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.69 kb
#include <bits/stdc++.h>
using namespace std;

const int N = 20000;

#define pc(x) putchar_unlocked(x);
#define pb push_back
#define X first
#define Y second
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
typedef pair <int,int> PII;

inline int readChar();
template <class T = int> inline T readInt();
template <class T> inline void writeInt( T x, char end = 0 );
inline void writeChar( int x );
inline void writeWord( const char *s );

/** Read */

static const int buf_size = 4096;

inline int getChar() {
    static char buf[buf_size];
    static int len = 0, pos = 0;
    if (pos == len)
        pos = 0, len = fread(buf, 1, buf_size, stdin);
    if (pos == len)
        return -1;
    return buf[pos++];
}

inline int readChar() {
    int c = getChar();
    while (c <= 32)
        c = getChar();
    return c;
}

template <class T>
inline T readInt() {
    int s = 1, c = readChar();
    T x = 0;
    if (c == '-')
        s = -1, c = getChar();
    while ('0' <= c && c <= '9')
        x = x * 10 + c - '0', c = getChar();
    return s == 1 ? x : -x;
}

/** Write */

static int write_pos = 0;
static char write_buf[buf_size];

inline void writeChar( int x ) {
    if (write_pos == buf_size)
        fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
    write_buf[write_pos++] = x;
}

template <class T>
inline void writeInt( T x, char end ) {
    if (x < 0)
        writeChar('-'), x = -x;

    char s[24];
    int n = 0;
    while (x || !n)
        s[n++] = '0' + x % 10, x /= 10;
    while (n--)
        writeChar(s[n]);
    if (end)
        writeChar(end);
}

inline void writeWord( const char *s ) {
    while (*s)
        writeChar(*s++);
}

struct Flusher {
    ~Flusher() {
        if (write_pos)
            fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
    }
} flusher;

int n, q;
vector <short> t[N];
vector <int> orderx, order[N];
PII P[N];

short gety(int x, int y) {
    short res = 0;
    int v = upper_bound(order[x].begin(),order[x].end(),y-1) - order[x].begin();
    if (v < order[x].size() && order[x][v] == y) v++;
    for (y = v; y; y -= (y & -y)) res += t[x][y-1];
    return res;
}
short get(int x, int y) {
    short res = 0;
    int v = lower_bound(orderx.begin(),orderx.end(),x) - orderx.begin();
    if (v < orderx.size() && orderx[v] == x) v++;
    for (x = v; x; x -= (x & -x)) res += gety(x,y);
    return res;
}

void update(int x, int y) {
    for (;x <= n; x += (x & -x)) {
        int v = upper_bound(order[x].begin(),order[x].end(),y-1) - order[x].begin();
        if (v < order[x].size() && order[x][v] == y) v++;
        for (;v <= order[x].size(); v += (v & -v)) t[x][v-1]++;
    }
}

int main() {
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    n = readInt();
    rep(i,0,n) P[i].X = readInt(), P[i].Y = readInt();
    sort(P,P+n);
    int id = 0;
    rep(i,0,n) {
        if (orderx.empty() || orderx.back() != P[i].X) orderx.pb(P[i].X), P[i].X = ++id;
        else P[i].X = id;
    }
    sort(P,P+n,[&] (PII a, PII b) { return a.Y < b.Y; });
    rep(i,0,n) {
        for (int x = P[i].X; x <= n; x += (x & -x)) {
            order[x].pb(P[i].Y);
            t[x].pb(0);
        }
    }
    rep(i,0,n) update(P[i].X,P[i].Y);

    q = readInt();
    while (q--) {
        int x1, y1, x2, y2;
        x1 = readInt(), y1 = readInt(), x2 = readInt(), y2 = readInt();
        //printf("%d\n",get(x2,y2) - get(x2,y1-1) - get(x1-1,y2) + get(x1-1,y1-1));
        int v = get(x2,y2) - get(x2,y1-1) - get(x1-1,y2) + get(x1-1,y1-1);
        writeInt(v,'\n');
    }
}