Cod sursa(job #2128684)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 11 februarie 2018 22:25:48
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.92 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;
    int Y1,Y2;
    int where;
    int type;
    bool operator < (const event &other)const{
        if(x != other.x){
            return x < other.x;
        }
        if(other.type != type){
            return type < other.type;
        }
        if(Y1 != other.Y1){
            return Y1 < other.Y1;
        }
        if(Y2 != other.Y2){
            return Y2 < other.Y2;
        }
        return where < other.where;
    }
};
int N;
int M;
int AIB[2 * NMAX + 9];
int X[NMAX + 5];
int Y[NMAX + 5];
int X1[MMAX + 5];
int Y1[MMAX + 5];
int X2[MMAX + 5];
int Y2[MMAX + 5];
int R[MMAX + 5];
vector<event> V;
vector<pair<int,int> > tmp;
vector<int> nearestLeft;
vector<int> nearestRight;
void u(int pos){
    for(;pos <= (int)tmp.size();pos += (-pos) & pos){
        AIB[pos]++;
    }
}
int q(int pos){
    int rez = 0;
    for(;pos;pos -= (pos) & -pos){
        rez += AIB[pos];
    }
    return rez;
}
int main(){
    fscanf(f,"%d",&N);
    for(int i = 1;i <= N;i++){
        fscanf(f,"%d %d",&X[i],&Y[i]);
        tmp.push_back({Y[i],0});
    }
    fscanf(f,"%d",&M);
    for(int i = 1;i <= M;i++){
        fscanf(f,"%d %d %d %d",&X1[i],&Y1[i],&X2[i],&Y2[i]);
        tmp.push_back({Y1[i],1});
        tmp.push_back({Y2[i],1});
    }
    tmp.push_back({-2000000001,0});
    tmp.push_back({2000000001,0});
    sort(tmp.begin(),tmp.end());
    tmp.resize(unique(tmp.begin(),tmp.end()) - tmp.begin());
    nearestLeft.resize(tmp.size());
    nearestRight.resize(tmp.size());
    int last = 0;
    for(int i = 0;i < (int)tmp.size();i++){
        if(!tmp[i].second){
            last++;
        }
        nearestLeft[i] = last;
    }
    last++;
    for(int i = (int)tmp.size();i;i--){
        if(!tmp[i].second){
            last--;
        }
        nearestRight[i] = last;
    }
    for(int i = 1;i <= N;i++){
        Y[i] = nearestLeft[lower_bound(tmp.begin(),tmp.end(),make_pair(Y[i],0)) - tmp.begin()];
        V.push_back({X[i],Y[i],0,0,0});
    }
    for(int i = 1;i <= M;i++){
        Y1[i] = nearestLeft[lower_bound(tmp.begin(),tmp.end(),make_pair(Y1[i],0)) - tmp.begin()];
        Y2[i] = nearestLeft[lower_bound(tmp.begin(),tmp.end(),make_pair(Y2[i],0)) - tmp.begin()];
        V.push_back({X1[i],Y1[i],Y2[i],i,-1});
        V.push_back({X2[i],Y1[i],Y2[i],i,1});
    }
    sort(V.begin(),V.end());
    for(auto it:V){
        if(it.type == 0){
            u(it.Y1);
        }
        else{
            if(Y2 < Y1){
                continue;
            }
            R[it.where] += (q(it.Y2) - q(it.Y1 - 1)) * it.type;
        }
    }
    for(int i = 1;i <= M;i++){
        fprintf(g,"%d\n",R[i]);
    }
    fclose(f);
    fclose(g);
    return 0;
}