Cod sursa(job #2879861)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 29 martie 2022 08:53:51
Problema Zoo Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <bits/stdc++.h>
#define z(n) ((n^(n-1))&n)
#define nmax 16005
#define mmax 100005
using namespace std;

ifstream f("zoo.in");
ofstream g("zoo.out");

int aib[nmax],k,n,m;
int i,j;
void up(const int &p,const int &v)
{
    if(p==0) return;
    for(j=p;j<=n;j+=z(j)) aib[j]+=v;
}

int qer(const int &p)
{
    int ans=0;
    for(j=p;j>0;j-=z(j)) ans+=aib[j];
    return ans;
}

struct nod{

    int x,y,c=0,id;
    nod(){}
    nod(int x, int y, int c)
    {
        this->x=x;
        this->y=y;
        this->c=c;
    }
};


nod v[nmax+mmax*4];
int ix[nmax+mmax*4];
int ans[mmax];
int srt[nmax];

bool cmpx(const int &a, const int &b)
{
    return v[a].x<v[b].x||((v[a].x==v[b].x&&v[a].y<v[b].y)||(v[a].x==v[b].x&&v[a].y==v[b].y&&v[a].c==0));
}
bool cmpy(const int &a, const int &b)
{
    return v[a].y<v[b].y;
}


int32_t main()
{
    ios_base::sync_with_stdio(false);
    f.tie(NULL);
    f>>n;
    for(i=1;i<=n;i++)
    {
        ++k; f>>v[k].x>>v[k].y;
        ix[k]=k;
    }
    f>>m;
    int a,b,c,d;
    sort(ix+1,ix+k+1,cmpy);
    for(i=1;i<=k;i++) {v[ix[i]].id=i;srt[i]=v[ix[i]].y;}
    for(i=1;i<=m;i++)
    {
        f>>a>>b>>c>>d;
        v[++k]=nod(a-1,b-1,i); ix[k]=k;
        v[++k]=nod(a-1,d,-i); ix[k]=k;
        v[++k]=nod(c,b-1,-i); ix[k]=k;
        v[++k]=nod(c,d,i); ix[k]=k;
    }

    /*for(i=1;i<=k;i++) cout<<ix[i]<<' ';
    cout<<'\n';
    for(i=1;i<=k;i++) cout<<ix[i]<<' ';
    cout<<'\n';*/

    sort(ix+1,ix+k+1,cmpx);

    for(i=1;i<=k;i++)
    {
        //cout<<ix[i]<<' ';
        if(v[ix[i]].c==0) up(v[ix[i]].id,1);
        if(v[ix[i]].c<0) ans[-v[ix[i]].c]-=qer(upper_bound(srt+1,srt+n+1,v[ix[i]].y)-srt-1);
        if(v[ix[i]].c>0) ans[v[ix[i]].c]+=qer(upper_bound(srt+1,srt+n+1,v[ix[i]].y)-srt-1);
    }
    for(i=1;i<=m;i++) g<<ans[i]<<'\n';
    return 0;
}