Cod sursa(job #2886264)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 7 aprilie 2022 15:11:19
Problema Zoo Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 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<=k;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];

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;
    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;
    }
    sort(ix+1,ix+k+1,cmpy);
    for(i=1;i<=k;i++) v[ix[i]].id=i;

    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(v[ix[i]].id);
        if(v[ix[i]].c>0) ans[v[ix[i]].c]+=qer(v[ix[i]].id);
    }
    for(i=1;i<=m;i++) g<<ans[i]<<'\n';
    return 0;
}