Cod sursa(job #1224413)

Utilizator danalex97Dan H Alexandru danalex97 Data 30 august 2014 22:03:56
Problema Zoo Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 16010;
const int M = 100010;
const int inf = 2000000001;

ifstream F("zoo.in");
ofstream G("zoo.out");

int n,m;

struct query
{
    int x,y,sgn,ord;
};

query make(int x,int y,int sgn,int ord)
{
    query q;
    q.x = x;
    q.y = y;
    q.sgn = sgn;
    q.ord = ord;
    return q;
}

bool cmp(query a,query b)
{
    return a.x < b.x || ( a.x == b.x && a.sgn == 0 && b.sgn != 0 );
}

vector<query> v;
vector<int> ys;
int AIB[N],ans[M];

void add(int x)
{
    if ( x == 0 ) return;
    for (int i=x;i<N;i+=(i&(-i)))
        AIB[i]++;
}

int ask(int x)
{
    if ( x == 0 ) return 0;
    int ans = 0;
    for (int i=x;i>0;i-=(i&(-i)))
        ans += AIB[i];
    return ans;
}

int main()
{
    F>>n;
    //ys.push_back(-inf);
    for (int i=1,x,y;i<=n;++i)
    {
        F>>x>>y;
        ys.push_back(y);
        v.push_back( make(x,y,0,0) );
    }
    F>>m;
    for (int i=1,x,y,x2,y2;i<=m;++i)
    {
        F>>x>>y>>x2>>y2;
        v.push_back( make(x-1,y-1,1,i) );
        v.push_back( make(x2,y-1,-1,i) );
        v.push_back( make(x-1,y2,-1,i) );
        v.push_back( make(x2,y2,1,i) );
    }
    sort(ys.begin(),ys.end());
    ys.erase( unique(ys.begin(),ys.end()) , ys.end() );
    sort(v.begin(),v.end(),cmp);
    for (size_t i=0;i<v.size();++i)
    {
        query a = v[i];
        int y = upper_bound(ys.begin(),ys.end(),a.y) - ys.begin();
        if ( y > ys.size() ) y = ys.size();
        if ( a.sgn == 0 )
            add(y);
        else
            ans[a.ord] += ask(y) * a.sgn;
    }
    for (int i=1;i<=m;++i)
        G<<ans[i]<<'\n';
}