Cod sursa(job #2022260)

Utilizator refugiatBoni Daniel Stefan refugiat Data 16 septembrie 2017 09:54:01
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream si("zoo.in");
ofstream so("zoo.out");
pair<int,int> v[16001];
vector<int>a[16*16001],x;
int lf,rt;
void upd(int nod,int st,int dr)
{
    if(st==dr)
    {
            a[nod].push_back(v[st].second);
            return;
    }
    int mij=(st+dr)>>1;
    upd(2*nod,st,mij);
    upd(2*nod+1,mij+1,dr);
    a[nod].resize(a[2*nod].size()+a[2*nod+1].size());
    merge(a[2*nod].begin(),a[2*nod].end(),a[2*nod+1].begin(),a[2*nod+1].end(),a[nod].begin());
}
int rez,l,r,y,b;
void querry(int nod,int st,int dr)
{
    if(lf<=st&&dr<=rt)
    {
        l=lower_bound(a[nod].begin(),a[nod].end(),y)-a[nod].begin();
        r=upper_bound(a[nod].begin(),a[nod].end(),b)-a[nod].begin();
        rez=rez-l+r;
        return;
    }
    if(st==dr) return;
    int mij=(st+dr)>>1;
    if (lf<=mij) querry(2*nod,st,mij);
    if (mij<rt) querry(2*nod+1,mij+1,dr);
}
int main()
{
    int n;
    si>>n;
    for(int i=1;i<=n;i++)
    {
        si>>v[i].first>>v[i].second;
        x.push_back(v[i].first);
    }
    sort(x.begin(),x.end());
    sort(v+1,v+n+1);
    int m;
    si>>m;
    upd(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int t1,t2;
        si>>t1>>y>>t2>>b;
        rez=0;
        lf=lower_bound(x.begin(),x.end(),t1)-x.begin()+1;
        rt=upper_bound(x.begin(),x.end(),t2)-x.begin();
        querry(1,1,n);
        so<<rez<<'\n';
    }
    return 0;
}