Cod sursa(job #2811216)

Utilizator marcumihaiMarcu Mihai marcumihai Data 1 decembrie 2021 14:54:17
Problema Zoo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.26 kb
#include <bits/stdc++.h>

using namespace std;

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

struct ceva
{
    int x;
    int y;
    int indice;
    int poznorm;

};
ceva a[16005];


struct qu
{
    int dr;
    int jos;
    int indice;
    int semn;
};
qu x;

int n;
int q;

int cmp (ceva A, ceva B)
{
    if(A.y<=B.y)
        return 1;
    return 0;

}

ceva ajut[16005];


void chestie()
{

    int val=0;
    ajut[0].y=-INT_MAX;
    for(int i=1; i<=n; ++i)
    {
        if(ajut[i].y!=ajut[i-1].y)
            ++val;

        int ind=ajut[i].indice;
        a[ind].y=val;
        ajut[i].poznorm=val;
    }

}

qu b[150005];

int cb(int val)
{
    int st=1;
    int dr=n;
    int mij=(st+dr)/2;

    while(st<=dr)
    {
        if(ajut[mij].y<=val && ajut[mij+1].y>val)
            return ajut[mij].poznorm;
        if(ajut[mij].y>val)
            dr=mij-1;
        else
            st=mij+1;
        mij=(st+dr)/2;
    }
    return 0;

}
int aint[400005];


void Update(int nod, int st, int dr, int val)
{
    if(st==dr)
    {
        aint[nod]++;
        return;
    }
    int mij=(st+dr)/2;
    if(mij>=val)
    {
        Update(2*nod  , st , mij , val);
        aint[nod]=aint[2*nod]+aint[2*nod+1];
    }
    else
    {
        Update(2*nod+1  , mij+1 , dr , val);
        aint[nod]=aint[2*nod]+aint[2*nod+1];
    }
}

int Query(int nod , int st , int dr , int val)
{

    if(st==dr)
    {
         return aint[nod];

    }
    int mij=(st+dr)/2;
    if(val<=mij)
        return Query(2*nod , st , mij , val);
    else
        return aint[2*nod]+Query(2*nod+1 , mij+1 , dr , val);
}




int cmp2(qu A, qu B)
{
    if(A.dr<B.dr)
        return 1;
    return 0;
}

int rasp[100005];

int cont;

int cmp3(ceva A , ceva B)
{
    if(A.x<B.x)
        return 1;
    return 0;
}

int main()
{
    f>>n;
    for(int i=1; i<=n; ++i)
    {
        f>>a[i].x;
        f>>a[i].y;
        a[i].indice=i;
        ajut[i]=a[i];
    }
    ajut[n+1].y=INT_MAX;
    sort(ajut+1, ajut+n+1, cmp);
    chestie();

    f>>q;
    for(int i=1; i<=q; ++i)
    {
        int A,B,C,D;
        f>>B>>A>>D>>C;

        qu x;
        x.dr=D;
        x.jos=cb(A-1);
        x.indice=i;
        x.semn=-1;
        b[++cont]=x;

        x.dr=B-1;
        x.jos=cb(C);
        x.indice=i;
        x.semn=-1;
        b[++cont]=x;

        x.dr=B-1;
        x.jos=cb(A-1);
        x.indice=i;
        x.semn=1;
        b[++cont]=x;

        x.dr=D;
        x.jos=cb(C);
        x.indice=i;
        x.semn=1;
        b[++cont]=x;

    }


    sort(b+1, b+cont+1, cmp2);

    for(int i=1;i<=n;++i)
        cout<<a[i].x<<" "<<a[i].y<<"\n";

    sort(a+1 , a+n+1 , cmp3);
    int bagate=1;
    for(int i=1; i<=cont; ++i)
    {
        while(a[bagate].x<=b[i].dr && bagate<=n)
        {

            Update(1, 1, n, a[bagate].y);
            ++bagate;
        }
        int rez=0;
        if(b[i].jos!=0)
         rez=Query(1, 1, n, b[i].jos);

        cout<<b[i].dr<<" "<<b[i].jos<<" "<<b[i].indice<<" "<<b[i].semn<<" "<<rez<<"\n";

        rasp[b[i].indice]+=rez*b[i].semn;
    }

    for(int i=1; i<=q; ++i)
        g<<rasp[i]<<"\n";


    return 0;
}