Cod sursa(job #2882354)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 31 martie 2022 12:51:10
Problema Zoo Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <bits/stdc++.h>
#define nmax 16005
#define mmax 100005
using namespace std;

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

int p=0;

int queries[mmax];
int arb[(mmax*2+nmax)<<2];
int n,m;
int ind;

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;
    }
    void output()
    {
        out<<x<<' '<<y<<' '<<query<<' '<<queryid<<' '<<op<<'\n';
    }
}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()
{
    in>>n;
    for(int i=0;i<n;i++)
    {
        int x,y;
        in>>x>>y;
        puncte[p++]=punct(x,y);
    }
    in>>m;
    for(int i=1;i<=m;i++)
    {
        int x1,y1,x2,y2;
        in>>x1>>y1>>x2>>y2;
        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';
    }
}