Cod sursa(job #2810197)

Utilizator marcumihaiMarcu Mihai marcumihai Data 28 noiembrie 2021 20:15:42
Problema Zoo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <bits/stdc++.h>

using namespace std;

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")




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

int n;
struct punct
{
    int y;
    int x;
};
punct a[20005];

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



struct query
{
    int dr;
    int jos;
    int indice;
    int semn;


};
punct qu[100005];

int cmp2(query A, query B)
{
    if(A.dr<B.dr)
        return 1;
    return 0;
}
multiset <int> s;

query b[500005];
int cont=0;
int rasp[100005];
int q;





int main()
{
    ios_base::sync_with_stdio(false);
    f.tie(NULL);
    f>>n;
    for(int i=1; i<=n; ++i)
    {
        f>>a[i].x>>a[i].y;
    }
    sort(a+1, a+n+1, cmp);
    f>>q;
    for(int i=1; i<=q; ++i)
    {
        int A,B,C,D;
        f>>B>>A>>D>>C;
        query x;
        x.dr=D;
        x.jos=A;
        x.indice=i;
        x.semn=1;
        b[++cont]=x;

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

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

        x.dr=D;
        x.jos=C+1;
        x.indice=i;
        x.semn=-1;
        b[++cont]=x;
    }
    sort(b+1, b+cont+1, cmp2);



    int pctcur=1;
    for(int i=1; i<=cont; ++i)
    {
        int limdr=b[i].dr;
        while(a[pctcur].x<=b[i].dr && pctcur<=n)
        {
            s.insert(a[pctcur].y);
            ++pctcur;
        }

        int r=distance(s.begin(), s.lower_bound(b[i].jos));


        rasp[b[i].indice]+=(pctcur-r-1)*b[i].semn;


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


    return 0;
}