Cod sursa(job #2407134)

Utilizator CharacterMeCharacter Me CharacterMe Data 16 aprilie 2019 15:51:53
Problema Zoo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.76 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);
class BTree{
    vector<int> V[64001];
    void Inter(int S, int D, int position){
        int mid=(S+D)/2;
        if(S==D) {V[position].push_back(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]<=V[2*position+1][j])
                {V[position].push_back(V[2*position][i]); ++i;}
            else {V[position].push_back(V[2*position+1][j]); ++j;}
        }
        while(i<V[2*position].size()) {V[position].push_back(V[2*position][i]); ++i;}
        while(j<V[2*position+1].size()){V[position].push_back(V[2*position+1][j]); ++j;}
        return;
    }
    int BS2(int S, int D, int val, int i){
        if(val<=V[i][S]) return S;
        if(val>=V[i][D]) return D;
        int mid=(S+D)/2;
        if(S==D) return mid;
        if(val==V[i][mid] || (val<V[i][mid] && V[i][mid-1]<val)) return mid;
        if(V[i][mid]<val && val<V[i][mid+1]) return mid+1;
        if(val<V[i][mid]) return BS2(S, mid-1, val, i);
        else return BS2(mid+1, D, val, i);
    }
    int Parc(int left, int right, int y1, int y2, int a, int b, int position){
        if(y1>V[position][V[position].size()-1] || y2<V[position][0]) return 0;
        int mid=(a+b)/2;
        int pozy1, pozy2;
        pozy1=BS2(0, V[position].size()-1, y1, position);
        pozy2=BS2(0, V[position].size()-1, y2, position);
        while(pozy1-1>=0 && V[position][pozy1-1]==V[position][pozy1]) --pozy1;
        while(pozy2+1<V[position].size() && V[position][pozy2+1]==V[position][pozy2]) ++pozy2;
        if(left==a && right==b) return pozy2-pozy1+1;
        else if(right<=mid) return Parc(left, right, y1, y2, a, mid, 2*position);
        else if(left>mid) return Parc(left, right, y1, y2, mid+1, b, 2*position+1);
        else return Parc(left, mid, y1, y2, a, mid, 2*position)+Parc(mid+1, right, y1, y2, 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 sol=Parc(a, b, y1, y2, 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);
        while(poz1-1>=1 && List[poz1-1].first==List[poz1].first) --poz1;
        while(poz2+1<=N && List[poz2+1].first==List[poz2].first) ++poz2;
        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);
}