Cod sursa(job #2879513)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 28 martie 2022 18:03:55
Problema Zoo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <bits/stdc++.h>
#define z(n) ((n^(n-1))&n)
#define nmax 16001
#define mmax 100001
using namespace std;

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

int aib[nmax+mmax],k,n,m;

void up(const int &p,const int &v)
{
    for(int i=p;i<=k;i+=z(i)) aib[i]+=v;
}

int qer(const int &p)
{
    int ans=0;
    for(int i=p;i>0;i-=z(i)) ans+=aib[i];
    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;
    }
};

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

int i,j;
nod v[nmax];
int ans[mmax];
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        ++k; f>>v[k].x>>v[k].y;
    }
    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);
        v[++k]=nod(a-1,d,-i);
        v[++k]=nod(c,b-1,-i);
        v[++k]=nod(c,d,i);
    }
    sort(v+1,v+1+k,cmpy);
    for(int i=1;i<=k;i++) v[i].id=i;
    sort(v+1,v+k+1,cmpx);
    for(int i=1;i<=k;i++)
    {
        if(v[i].c==0) up(v[i].id,1);
        if(v[i].c<0) ans[-v[i].c]-=qer(v[i].id);
        if(v[i].c>0) ans[v[i].c]+=qer(v[i].id);
    }
    for(int i=1;i<=m;i++) g<<ans[i]<<'\n';
    return 0;
}