Cod sursa(job #2898130)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 6 mai 2022 08:48:20
Problema Zoo Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.69 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[(mmax*2+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;
    bool query,op;
    punct(int x=0,int y=0,bool query=0,int queryid=0,bool op=0)
    {
        this->x=x;
        this->y=y;
        this->query=query;
        this->queryid=queryid;
        this->op=op;
    }
    bool operator <(const punct other)
    {
        if(x!=other.x)return x<other.x;
        return !query;
    }
}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;i++)
    {
        int val=puncte[i].y;
        puncte[i].y=ind;
        if(val<puncte[i+1].y)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);
    }
    m=nxtint();
    for(int i=1;i<=m;i++)
    {
        int x1=nxtint(),y1=nxtint(),x2=nxtint(),y2=nxtint();
        puncte[p++]=punct(x1-1,y1-1,1,i,0);
        puncte[p++]=punct(x2,y2,1,i,0);
        puncte[p++]=punct(x1-1,y2,1,i,1);
        puncte[p++]=punct(x2,y1-1,1,i,1);
    }
    normalizey();
    sort(puncte,puncte+p);
    for(int i=0;i<p;i++)
    {
        if(!puncte[i].query)
        {
            update(0,ind,1,puncte[i].y,1);
        }
        else
        {
            if(puncte[i].op)
            {
                queries[puncte[i].queryid]-=q(0,ind,0,puncte[i].y,1);
            }
            else
            {
                queries[puncte[i].queryid]+=q(0,ind,0,puncte[i].y,1);
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        out<<queries[i]<<'\n';
    }
}