Cod sursa(job #2407107)

Utilizator CharacterMeCharacter Me CharacterMe Data 16 aprilie 2019 15:14:23
Problema Zoo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.78 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
int N, M, i, j;
pair<int, int> List[16001];
void QSort(int S, int D);
int Arrange(int S, int D);
struct Trio{
    int pozLeft, pozRight, Y;
};
Trio make_trio(int pL, int pR, int pY){
    Trio T;
    T.pozLeft=pL;
    T.pozRight=pR;
    T.Y=pY;
    return T;
}
class BTree{
    vector<Trio> V[64001];
    void Inter(int S, int D, int position){
        int mid=(S+D)/2;
        if(S==D) {V[position].push_back(make_trio(0, 0, List[S].second)); return;}
        Inter(S, mid, 2*position);
        Inter(mid+1, D, 2*position+1);
        int i=0, j=0;
        while(i<V[2*position].size() && j<V[2*position+1].size()){
            if(V[2*position][i].Y<=V[2*position+1][j].Y)
                {V[position].push_back(make_trio(i, j, V[2*position][i].Y)); ++i;}
            else {V[position].push_back(make_trio(i, j, V[2*position+1][j].Y)); ++j;}
        }
        while(i<V[2*position].size()) {V[position].push_back(make_trio(i, j-1, V[2*position][i].Y)); ++i;}
        while(j<V[2*position+1].size()){V[position].push_back(make_trio(i-1, j, V[2*position+1][j].Y)); ++j;}
        return;
    }
    int Parc(int left, int right, int y1, int y2, int pozy1, int pozy2, int a, int b, int position){
        int mid=(a+b)/2;
        while(y1<V[position][pozy1].Y && pozy1+1<V[position].size()) ++pozy1;
        while(pozy1-1>=0 && y1>=V[position][pozy1-1].Y) --pozy1;
        while(pozy2+1<V[position].size() && y2>=V[position][pozy2+1].Y) ++pozy2;
        while(y2<=V[position][pozy2].Y && pozy2>0) --pozy2;
        if(left==a && right==b) return pozy2-pozy1+1;
        if(right<=mid) return Parc(left, right, y1, y2, V[position][pozy1].pozLeft, V[position][pozy2].pozLeft, a, mid, 2*position);
        else if(left>mid) return Parc(left, right, y1, y2, V[position][pozy1].pozRight, V[position][pozy2].pozRight, mid+1, b, 2*position+1);
        else return Parc(left, mid, y1, y2, V[position][pozy1].pozLeft, V[position][pozy2].pozLeft, a, mid, 2*position)+Parc(mid+1, right, y1, y2, V[position][pozy1].pozRight, V[position][pozy2].pozRight, mid+1, b, 2*position+1);
    }
public:
    void Build(){
        Inter(1, N, 1);
        return;
    }
    void Get(int a, int b, int y1, int y2){
        int i, pozy1, pozy2;
        for(i=0; i<V[1].size() && y1>V[1][i].Y; ++i); pozy1=i;
        for(i=V[1].size()-1; i>=0 && y2<V[1][i].Y; --i); pozy2=i;
        int sol=Parc(a, b, y1, y2, pozy1, pozy2, 1, N, 1);
        fout<<sol<<"\n";
        return;
    }
};
BTree Arb;
int BS1(int S, int D, int val);
int main()
{
    fin>>N;
    for(i=1; i<=N; ++i) fin>>List[i].first>>List[i].second;
    QSort(1, N);
    Arb.Build();
    fin>>M;
    for(i=1; i<=M; ++i){
        int a, b, c, d;
        fin>>a>>b>>c>>d;
        int poz1=BS1(1, N, a), poz2=BS1(1, N, c);
        Arb.Get(poz1, poz2, b, d);
    }
    return 0;
}
void QSort(int S, int D){
    if(S<D){
        int p=Arrange(S, D);
        QSort(S, p-1);
        QSort(p+1, D);
    }
    return;
}
int Arrange(int S, int D){
    int pS=0, pD=1;
    while(S<D){
        if(List[S].first>List[D].first){
            swap(List[S].first, List[D].first);
            swap(List[S].second, List[D].second);
            swap(pS, pD);
        }
        S+=pS;
        D-=pD;
    }
    return S;
}
int BS1(int S, int D, int val){
    if(val<=List[S].first) return S;
    if(val>=List[D].first) return D;
    int mid=(S+D)/2;
    if(S==D) return mid;
    if(val==List[mid].first || (val<List[mid].first && List[mid-1].first<val)) return mid;
    if(List[mid].first<val && val<List[mid+1].first) return mid+1;
    if(val<List[mid].first) return BS1(S, mid-1, val);
    else return BS1(mid+1, D, val);
}