Cod sursa(job #1224414)

Utilizator danalex97Dan H Alexandru danalex97 Data 30 august 2014 22:04:31
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.58 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,sz;
vector<int> ys,xs;
vector< pair<int,int> > v;
vector<int> vl[N*4],p1[N*4],p2[N*4];

int normy(int y)
{
    y = upper_bound(ys.begin(),ys.end(),y) - ys.begin();
    if ( y > int(ys.size()) ) y = ys.size();
    return y;
}

int normx(int x)
{
    x = upper_bound(xs.begin(),xs.end(),x) - xs.begin();
    if ( x > int(xs.size()) ) x = xs.size();
    return x;
}

int norm(int x)
{
    if ( x == 0 ) return -1;
    x = upper_bound(vl[1].begin(),vl[1].end(),x) - vl[1].begin();
    if ( x > int(vl[1].size()) ) x = vl[1].size();
    return x;
}

void add(int n,int l,int r,int p,int v)
{
    if ( l > p || r < p ) return;
    if ( l == r )
    {
        vl[n].push_back(v);
        //cerr<<l<<' '<<r<<"\n";
        return;
    }
    int m = ( l + r ) / 2;
    add(n*2,l,m,p,v);
    add(n*2+1,m+1,r,p,v);
}

void asort(int n,int l,int r)
{
    if ( l == r )
    {
        sort(vl[n].begin(),vl[n].end());
        //cerr<<l<<' '<<r<<':'<<'\n';
        //for (int i=0;i<int(vl[n].size());++i) cerr<<vl[n][i]<<' '; cerr<<'\n';
        return;
    }
    int m = ( l + r ) / 2;
    asort(n*2,l,m);
    asort(n*2+1,m+1,r);

    int ln = n*2 , rn = ln+1;
    int i1 = 0, i2 = 0;
    while ( i1 < int(vl[ln].size()) && i2 < int(vl[rn].size()) )
    {
        if ( vl[ln][i1] < vl[rn][i2] )
        {
            vl[n].push_back(vl[ln][i1]);
            p1[n].push_back(i1);
            p2[n].push_back(-1);
            ++i1;
        } else
        if ( vl[ln][i1] > vl[rn][i2] )
        {
            vl[n].push_back(vl[rn][i2]);
            p1[n].push_back(-1);
            p2[n].push_back(i2);
            ++i2;
        } else
        {
            vl[n].push_back(vl[rn][i2]);
            vl[n].push_back(vl[ln][i1]);
            p1[n].push_back(i1);
            p1[n].push_back(i1);
            p2[n].push_back(i2);
            p2[n].push_back(i2);
            ++i1;
            ++i2;
        }
    }
    while ( i1 < int(vl[ln].size()) )
    {
        vl[n].push_back(vl[ln][i1]);
        p1[n].push_back(i1);
        p2[n].push_back(-1);
        ++i1;
    }
    while ( i2 < int(vl[rn].size()) )
    {
        vl[n].push_back(vl[rn][i2]);
        p1[n].push_back(-1);
        p2[n].push_back(i2);
        ++i2;
    }
    //cerr<<l<<' '<<r<<':'<<'\n';
    for (int i=1;i<int(vl[n].size());++i) p1[n][i] = max(p1[n][i-1],p1[n][i]);
    for (int i=1;i<int(vl[n].size());++i) p2[n][i] = max(p2[n][i-1],p2[n][i]);
    for (int i=int(vl[n].size())-2;i>=0;--i) if ( vl[ln][p1[n][i+1]] == vl[ln][p1[n][i]] ) p1[n][i] = p1[n][i+1];
    for (int i=int(vl[n].size())-2;i>=0;--i) if ( vl[rn][p2[n][i+1]] == vl[rn][p2[n][i]] ) p2[n][i] = p2[n][i+1];

    //for (int i=0;i<int(vl[n].size());++i) cerr<<vl[n][i]<<' ';cerr<<'\n';
    //for (int i=0;i<int(vl[n].size());++i) cerr<<p1[n][i]<<' ';cerr<<'\n';
    //for (int i=0;i<int(vl[n].size());++i) cerr<<p2[n][i]<<' ';cerr<<'\n';
}

int ask(int n,int l,int r,int il,int ir,int a,int b)
{
    if ( l > ir || r < il )
        return 0;
    if ( n == 1 )
    {
        a = norm(a);
        b = norm(b);
        if ( a > 0 ) a--;
        if ( b > 0 ) b--;
    }

    if ( il <= l && r <= ir )
    {
        //if ( a == -1 ) a = 0;
        //if ( b == -1 ) b = 0;
        return b - a;
    }
    int m = (l + r) /2,a2=0,b2=0;
    a2 = a == -1 ? -1 : p1[n][a], b2 = b == -1 ? -1 : p1[n][b];
    int v1 = ask(n*2,l,m,il,ir,a2,b2);
    a2 = a == -1 ? -1 : p2[n][a], b2 = b == -1 ? -1 : p2[n][b];
    int v2 = ask(n*2+1,m+1,r,il,ir,a2,b2);
    return v1 + v2;
}

int main()
{
    F>>n;
    for (int i=1,x,y;i<=n;++i)
    {
        F>>x>>y;
        ys.push_back(y);
        xs.push_back(x);
        v.push_back( make_pair(x,y) );
    }
    sort(ys.begin(),ys.end());
    sort(xs.begin(),xs.end());
    ys.erase( unique(ys.begin(),ys.end()) , ys.end() );
    xs.erase( unique(xs.begin(),xs.end()) , xs.end() );
    sz = xs.size();
    for (size_t i=0;i<v.size();++i)
    {
        int x = normx(v[i].first);
        int y = normy(v[i].second);
        add(1,1,sz,x,y);
    }
    asort(1,1,sz);
    F>>m;
    for (int i=1,x,y,x2,y2;i<=m;++i)
    {
        F>>x>>y>>x2>>y2;
        int ax = normx(x); if ( x > xs[ax-1] ) x = ax+1; else x = ax;
        x2 = normx(x2);
        y = normy(y-1);
        y2 = normy(y2);
        G<<ask(1,1,sz,x,x2,y,y2)<<'\n';
    }
}