Cod sursa(job #237747)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 30 decembrie 2008 17:28:31
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <stdio.h>
#include <set>
#include <algorithm>

#define maxn 420000
#define maxm 120000
#define mp make_pair

using namespace std;

long aib[maxn], q[maxm][5];
long x[maxn], y[maxn], idx[maxn], pq[maxn];
long n, m, i, j, k, a, b, c, d, l;

pair<long, pair<long, pair<long, long> > > per[maxn];

long lsb(long x)
{
    return (x&(x-1))^x;
}

void imp(long a, long b, long c, long d)
{
    per[l]=mp(a, mp(b, mp(c, d) ) );
}

void update(long x)
{
    while(x<=l)
    {
        aib[x]++;
        x+=lsb(x);
    }
}

long querry(long x)
{
    long s=0;
    while(x>0)
    {
        s+=aib[x];
        x=x-lsb(x);
    }
    return s;
}

int main()
{
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);
    scanf("%d", &n);
    for(i=1; i<=n; i++)
    {
        scanf("%d %d", &x[i], &y[i]);
        l++;
        imp(y[i], x[i], 0, 0);
    }
    scanf("%d", &m);
    for(i=1; i<=m; i++)
    {
        scanf("%d %d %d %d", &a, &b, &c, &d);
        a--;
        b--;
        // a cu b
        l++;
        imp(b, a, i, 1);
        // a cu d
        l++;
        imp(d, a, i, 2);
        // c cu b
        l++;
        imp(b, c, i, 3);
        // c cu d
        l++;
        imp(d, c, i, 4);
    }
    sort(per+1, per+l+1);
    k=l;
    l=0;
    for(i=1; i<=k; i++)
    {
        l++;
        a=i;
        b=per[i].second.first;
        c=per[i].second.second.first;
        d=per[i].second.second.second;
        imp(b, a, c, d);
    }
    sort(per+1, per+l+1);
    for(i=1; i<=l; i++)
    {
        a=i;
        b=per[i].second.first;
        c=per[i].second.second.first;
        d=per[i].second.second.second;
        if(c==0) update(b);
        else q[c][d]=querry(b);
    }
    for(i=1; i<=m; i++)
    {
        printf("%d\n", q[i][4]-q[i][3]-q[i][2]+q[i][1]);
    }
    return 0;
}