Cod sursa(job #3183886)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 13 decembrie 2023 17:31:42
Problema Zoo Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.89 kb
#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

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

const int NMAX=16e3+5;
const int MMAX=1e5+5;

struct eventz{
    int type;   ///-1 capst, 0 point, 1 capdr
    int x1;
    int y1;
    int x2;
    int y2;
    int ind;
}events[NMAX+2*MMAX];

int aib[NMAX];
int v[NMAX];
int norm[NMAX];
int ans[NMAX];

int xx[NMAX+2*MMAX];
int yy[NMAX+2*MMAX];

bool cmp(eventz a,eventz b)
{
    if(a.x1==b.x1)
    {
        if(a.type==b.type)
            return a.y1<b.y1;
        else
            return a.type<b.type;
    }
    return a.x1<b.x1;
}

int n;
int saiz;

int lsb(int x)
{
    return x&(-x);
}

void update(int p,int val)
{
    while(p<=saiz)
    {
        aib[p]+=val;
        p+=lsb(p);
    }
}

int query(int p)
{
    int s=0;
    while(p>0)
    {
        s+=aib[p];
        p-=lsb(p);
    }
    return s;
}

int normalizare1(int x)
{
    int st=1,dr=saiz,mij;
    while(st<=dr)
    {
        mij=st+dr;
        mij/=2;
        if(xx[mij]<x)
            st=mij+1;
        else if(xx[mij]>x)
            dr=mij-1;
        else
            return mij;
    }
    return st;
}

int normalizare2(int x)
{
    int st=1,dr=saiz,mij;
    while(st<=dr)
    {
        mij=st+dr;
        mij/=2;
        if(yy[mij]<x)
            st=mij+1;
        else if(yy[mij]>x)
            dr=mij-1;
        else
            return mij;
    }
    return st;
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    int i,q;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        int x,y;
        fin>>x>>y;
        events[++saiz]={0,x,y,0,0,0};
        xx[saiz]=x;
        yy[saiz]=y;
    }
    fin>>q;
    for(i=1;i<=q;i++)
    {
        int x1,y1,y2,x2;
        fin>>x1>>y1>>x2>>y2;
        events[++saiz]={-1,x1,y1,x1,y2,i};
        xx[saiz]=x1;
        yy[saiz]=y1;
        events[++saiz]={1,x2,y1,x2,y2,i};
        xx[saiz]=x2;
        yy[saiz]=y2;
    }
    sort(xx+1,xx+saiz+1);
    sort(yy+1,yy+saiz+1);
    for(i=1;i<=saiz;i++)
    {
        events[i].x1=normalizare1(events[i].x1);
        events[i].x2=normalizare1(events[i].x2);
        events[i].y1=normalizare2(events[i].y1);
        events[i].y2=normalizare2(events[i].y2);
    }
    sort(events+1,events+saiz+1,cmp);
    for(i=1;i<=saiz;i++)
    {
        if(events[i].type==0)
            update(events[i].y1,1);
        else if(events[i].type==-1)
            ans[events[i].ind]-=query(events[i].y2)-query(events[i].y1-1);
        else
            ans[events[i].ind]+=query(events[i].y2)-query(events[i].y1-1);
    }
    for(i=1;i<=q;i++)
        fout<<ans[i]<<"\n";
    fin.close();
    fout.close();
    return 0;
}