Cod sursa(job #1227554)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 10 septembrie 2014 20:21:34
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include<bits/stdc++.h>
using namespace std;

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

struct points
{
    int x,y;
};

struct drept
{
    int x,y,w,z;
    int indice;
};

struct comp
{
    bool operator () (const int& A,const int& B) const
        {
            return A>B;
        }
};

const int NMAX=16005;
const int MMAX=100005;

int n,m,sol[MMAX],c[NMAX];
vector<points>v[NMAX];
vector<points>::iterator it;
points a[NMAX];
drept b[MMAX];
multiset<int>s;
multiset<int,comp>p;
multiset<int>::iterator pit;

inline bool cmp(const points A,const points B)
{
    return A.x<B.x;
}

int main()
{
    int i,poz,aux,nr;
    points d;
    fin>>n;
    for (i=1;i<=n;i++) fin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);
    for (i=1;i<=n;i++) c[i]=a[i].x;
    fin>>m;
    for (i=1;i<=m;i++)
        {
            fin>>b[i].x>>b[i].y>>b[i].w>>b[i].z;
            b[i].indice=i;

            d.x=i;
            d.y=-1;
            poz=lower_bound(c+1,c+n+1,b[i].x)-c;
            poz--;
            v[poz].push_back(d);
            d.y=1;
            poz=upper_bound(c+1,c+n+1,b[i].w)-c;
            if (c[poz]>b[i].w || poz>n) poz--;
            v[poz].push_back(d);
        }

    for (i=1;i<=n;i++)
        {
            s.insert(a[i].y);
            for (it=v[i].begin();it!=v[i].end();it++)
                {
                    d=*it;
                    pit=lower_bound(s.begin(),s.end(),b[i].y);
                    nr=0;
                    while (pit!=s.end() && (*pit)>=b[d.x].y && (*pit)<=b[d.x].w)
                        {
                            nr++;
                            pit++;
                        }
                    if (d.y==-1) sol[d.x]-=nr;
                    else sol[d.x]+=nr;
                }
        }

    for (i=1;i<=m;i++) fout<<sol[i]<<"\n";
    return 0;
}