Cod sursa(job #2810195)

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

using namespace std;

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()
{
    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;
        }
      for(auto x:s)
            cout<<x<<" ";
        cout<<"\n";

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

        cout<<b[i].dr<<" "<<b[i].jos<<" "<<pctcur-r-1<<" "<<b[i].indice<<"\n\n";
        rasp[b[i].indice]+=(pctcur-r-1)*b[i].semn;


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


    return 0;
}