Cod sursa(job #2456486)

Utilizator Senth30Denis-Florin Cringanu Senth30 Data 14 septembrie 2019 14:34:29
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.72 kb
#include <bits/stdc++.h>
#define MAX 131072

using namespace std;
const int NMAX = 16010;
const int QMAX = 100010;

FILE *IN;

int N, M, K, Q, ans;
int Norm[NMAX], v2[NMAX], out[QMAX];
int tree[4 * QMAX];

struct per{
    int x, y;
    int sign, index;
};

per v[NMAX], query[4 * QMAX];

int pos, sign;
char f[MAX];

inline void Read(int &nr){
    sign = 0;
    nr = 0;
    while(f[pos] < '0' || f[pos] > '9'){
        if(f[pos] == '-') sign = 1;
        pos++;
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    while(f[pos] >= '0' && f[pos] <= '9'){
        nr = 10 * nr + f[pos++] - '0';
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    if(sign) nr =- nr;
}

int binsearch(int x){
    int st = 1, nd = K;
    int last, middle;
    while(st <= nd){
        middle = (st + nd) / 2;
        if(Norm[middle] <= x){
            st = middle + 1;
            last = middle;
        } else nd = middle - 1;
    }
    return last;
}

bool cmp(per a, per b){
    return a.x < b.x;
}

inline void normalizare(){
    sort(v2 + 1, v2 + N + 1);
    Norm[++K] = v2[1];
    for(int i = 2; i <= N; i++){
        while(v2[i] == Norm[K]) i++;
        if(i <= N)
            Norm[++K] = v2[i];
    }
    for(int i = 1; i <= N; i++)
        v[i].y = binsearch(v[i].y);
    sort(v + 1, v + N + 1, cmp);
}

inline void read(){
    Read(N);
    for(int i = 1; i <= N; i++){
        Read(v[i].x); Read(v[i].y);
        v2[i] = v[i].y;
    }
    normalizare();
    v[++N].x = 2e9;
    Read(M);
    per X1, X2;
    for(int i = 1; i <= M; i++){
        Read(X1.x); Read(X1.y);
        Read(X2.x); Read(X2.y);
        query[++Q].x = X2.x; query[Q].y = X1.y; query[Q].sign = 1; query[Q].index = i;
        query[++Q].x = X1.x - 1; query[Q].y = X2.y + 1; query[Q].sign = 1; query[Q].index = i;
        query[++Q].x = X1.x - 1; query[Q].y = X1.y; query[Q].sign = -1; query[Q].index = i;
        query[++Q].x = X2.x; query[Q].y = X2.y + 1; query[Q].sign = -1; query[Q].index = i;
    }
    sort(query + 1, query + Q + 1, cmp);
}

inline void Update(int node, int st, int nd, int poz, int val){
    if(st == nd){
        tree[node] += val;
    } else {
        int mid = (st + nd) / 2;
        if(poz <= mid) Update(2 * node, st, mid, poz, val);
        else Update(2 * node + 1, mid + 1, nd, poz, val);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
}

inline int Query(int node, int st, int nd, int A, int B){
    if(A <= st && nd <= B){
        ans += tree[node];
    } else {
        int mid = (st + nd) / 2;
        if(mid >= A) Query(2 * node, st, mid, A, B);
        if(mid + 1 <= B) Query(2 * node + 1, mid + 1, nd, A, B);
    }
}

int caut_bin(int val){
    int st = 1, nd = K;
    int mid;
    while(st < nd){
        mid = (st + nd) / 2;
        if(Norm[mid] < val)
            st = mid + 1;
        else nd = mid;
    }
    mid = (st + nd) / 2;
    if(Norm[mid] < val)
        mid++;
    return mid;
}

int main(){

    IN = fopen("zoo.in", "r");
    freopen("zoo.out", "w", stdout);

    read();
    int Lmax = 0, p = 1;
    for(int i = 1; i <= N; i++){
        while(query[p].x < v[i].x && p <= Q){
            ans = 0;
            int poz = caut_bin(query[p].y);
            if(poz <= Lmax)
                Query(1, 1, K, poz, Lmax);
            out[query[p].index] += query[p].sign * ans;
            p++;
        }
        int j = i;
        while(v[j].x == v[i].x){
            if(v[j].y > Lmax) Lmax = v[j].y;
            Update(1, 1, K, v[j].y, 1);
            j++;
        }
        if(j != i) i = j - 1;
    }
    for(int i = 1; i <= M; i++)
        printf("%d\n", out[i]);

    return 0;
}