Cod sursa(job #2907687)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 31 mai 2022 10:13:46
Problema Zoo Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.16 kb
#include <bits/stdc++.h>
#define nmax 16005
#define mmax 100005
using namespace std;
 
FILE *in=fopen("zoo.in","r");
ofstream out("zoo.out");
 
int p=0;
 
int queries[mmax];
int arb[nmax*2];
int n,m;
int ind;
 
const int SBUFF=4096;
char BUFF[SBUFF];
int ee=SBUFF;
bool ischar[128];
 
char nxtchar()
{
    if(ee==SBUFF)
    {
        fread(BUFF,SBUFF,1,in);
        ee=0;
    }
    return BUFF[ee++];
}

int nxtint()
{
    int neg=1;
    int nr=0;
    char c=' ';
    while(!ischar[c])c=nxtchar();
    if(c=='-')
    {
        neg=-1;
        c=nxtchar();
    }
    while(ischar[c])
    {
        nr=nr*10+c-'0';
        c=nxtchar();
    }
    return neg*nr;
}

struct punct
{
    int x,y,queryid,priority,tag;
    bool op;
    punct(int x=0,int y=0,int priority=0,int queryid=0,bool op=0,int tag=0)
    {
        this->x=x;
        this->y=y;
        this->priority=priority;
        this->queryid=queryid;
        this->op=op;
    }
    bool operator <(const punct &other)
    {
        if(x!=other.x)return x<other.x;
        return priority>other.priority;
    }
}puncte[mmax*4+nmax+5];

bool cmp(const punct &a,const punct &b)
{
    return a.y<b.y;
}

void update(int st,int dr,int val,int poz,int nod)
{
    if(st==dr)arb[nod]++;
    else
    {
        int mij=(st+dr)/2;
        if(poz<=mij)update(st,mij,val,poz,nod*2);
        else update(mij+1,dr,val,poz,nod*2+1);
        arb[nod]++;
    }
}

int q(int st,int dr,int l,int r,int nod)
{
    if(l>r)return 0;
    if(st==l&&dr==r)return arb[nod];
    int mij=(st+dr)/2;
    return q(st,mij,l,min(mij,r),nod*2)+q(mij+1,dr,max(mij+1,l),r,nod*2+1);
}

void normalizey()
{
    sort(puncte,puncte+p,cmp);
    for(int i=0;i<p;)
    {
        int yy=puncte[i].y;
        bool haspoint = 0;
        while(i<p && puncte[i].y==yy)
        {
            //cout<<i<<' ';
            if(puncte[i].queryid==0)haspoint=1;
            puncte[i].y=ind;
            //cout<<puncte[i].y<<' '<<puncte[i].queryid<<'\n';
            i++;
        } 
        if (haspoint)ind++;
    }
}

int main()
{
    for(int i='0';i<='9';i++)ischar[i]=1;
    ischar['-']=1;
    n=nxtint();
    for(int i=0;i<n;i++)
    {
        int x=nxtint(),y=nxtint();
        puncte[p++]=punct(x,y,1);
    }
    m=nxtint();
    for(int i=1;i<=m;i++)
    {
        int x1=nxtint(),y1=nxtint(),x2=nxtint(),y2=nxtint();
        puncte[p++]=punct(x1-1,y1,0,i,0,0);
        puncte[p++]=punct(x2+1,y2+1,2,i,0,0);
        puncte[p++]=punct(x1-1,y2+1,0,i,1,2);
        puncte[p++]=punct(x2+1,y1,2,i,1,1);
    }
    normalizey();
    sort(puncte,puncte+p);
    for(int i=0;i<p;i++)
    {
        if(!puncte[i].queryid)
        {
            update(0,ind,1,puncte[i].y,1);
        }
        else
        {
            if(puncte[i].op)
            {
                if(puncte[i].tag==1)queries[puncte[i].queryid]-=q(0,ind,0,puncte[i].y-1,1);
                else queries[puncte[i].queryid]-=q(0,ind,0,puncte[i].y-1,1);
            }
            else
            {
                if(puncte[i].tag==0)queries[puncte[i].queryid]+=q(0,ind,0,puncte[i].y-1,1);
                else queries[puncte[i].queryid]+=q(0,ind,0,puncte[i].y-1,1);
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        out<<queries[i]<<'\n';
    }
}