Cod sursa(job #2131093)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 14 februarie 2018 12:32:31
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
FILE *f = fopen("zoo.in","r");
FILE *g = fopen("zoo.out","w");
const int NMAX = 16000;
const int MMAX = 100000;
struct event{
    int x;
    short Y1,Y2;
    int where;
    short type;
    bool operator < (const event &other)const{
        if(x != other.x){
            return x < other.x;
        }
        return type < other.type;
    }
};
int N;
int M;
short AIB[NMAX + 9];
int X[NMAX + 5];
int Y[NMAX + 5];
short R[MMAX + 5];
vector<event> V;
vector<int> tmp;
int sz = 0;
void u(int pos){
    for(;pos <= sz;pos += (-pos) & pos){
        AIB[pos]++;
    }
}
int q(int pos){
    int rez = 0;
    for(;pos;pos -= pos & (-pos)){
        rez += AIB[pos];
    }
    return rez;
}
const int LEN = 131072;
int ind = LEN - 1;
char buff[LEN];
int i32(){
    int rez = 0,sgn = 1;
    while((buff[ind] < '0' || buff[ind] > '9') && buff[ind] != '-'){
        if(++ind >= LEN){
            ind = 0;
            fread(buff,1,LEN,f);
        }
    }
    if(buff[ind] == '-'){
        sgn = -1;
        if(++ind >= LEN){
            ind = 0;
            fread(buff,1,LEN,f);
        }
    }
    while(buff[ind] >= '0' && buff[ind] <= '9'){
        rez = rez * 10 + buff[ind] - '0';
        if(++ind >= LEN){
            ind = 0;
            fread(buff,1,LEN,f);
        }
    }
    return rez * sgn;
}
int main(){
    N = i32();
    for(int i = 1;i <= N;i++){
        X[i] = i32();
        Y[i] = i32();
        tmp.push_back(Y[i]);
    }
    tmp.push_back((2e9) + 1);
    tmp.push_back(-(2e9) - 1);
    sort(tmp.begin(),tmp.end());
    tmp.resize(unique(tmp.begin(),tmp.end()) - tmp.begin());
    sz = tmp.size();
    for(int i = 1;i <= N;i++){
        Y[i] = lower_bound(tmp.begin(),tmp.end(),Y[i]) - tmp.begin() + 1;
        V.push_back({X[i],Y[i],0,0,0});
    }
    M = i32();
    for(int i = 1;i <= M;i++){
        int X1,Y1,X2,Y2;
        X1 = i32();
        Y1 = i32();
        X2 = i32();
        Y2 = i32();
        int tmpY2 = Y2;
        Y1 = lower_bound(tmp.begin(),tmp.end(),Y1) - tmp.begin() + 1;
        Y2 = lower_bound(tmp.begin(),tmp.end(),Y2) - tmp.begin() + 1;
        if(tmp[Y2 - 1] != tmpY2){
            Y2--;
        }
        V.push_back({X1,Y1,Y2,i,-1});
        V.push_back({X2,Y1,Y2,i,1});
    }
    sort(V.begin(),V.end());
    for(auto it:V){
        if(it.type == 0){
            u(it.Y1);
        }
        else{
            if(it.Y2 < it.Y1){
                continue;
            }
            R[it.where] += (q(it.Y2) - (it.Y1 > 1 ? q(it.Y1 - 1) : 0)) * it.type;
        }
    }
    for(int i = 1;i <= M;i++){
        fprintf(g,"%d\n",R[i]);
    }
    fclose(f);
    fclose(g);
    return 0;
}