Cod sursa(job #1553872)

Utilizator cojocarugabiReality cojocarugabi Data 20 decembrie 2015 17:37:56
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
# include <bits/stdc++.h>
using namespace std;
int len[32005];
int v[32005];
int p[32005];
int *s[32005];
int cnt_v;
int a[16005],b[16005];
int go(int pos,int val)
{
    int ans = 0;
    for (int i = 1 << 15;i;i >>= 1)
        if (ans + i <= len[pos] && s[pos][ans+i] <= val) ans += i;
    return ans;
}
int bin(int val)
{
    int ans = 0;
    for (int i = 1 << 15;i;i >>= 1)
        if (ans + i <= cnt_v && v[ans+i] <= val) ans += i;
    if (ans <= cnt_v && v[ans] < val) ++ans;
    return ans;
}
void update_len(int i,int val)
{
    for (;i <= cnt_v;i += i&(-i)) p[i] += val;
}
int query_len(int i)
{
    int ans = 0;
    for (;i;i -= i&(-i)) ans += p[i];
    return ans;
}
void update_arb(int i,int val)
{
    for (;i <= cnt_v;i += i&(-i)) s[i][++len[i]] = val;
}
int query_arb(int i,int l,int r)
{
    if (i<0) return 0;
    int ans = 0;
    for (;i;i -= i&(-i))
    {
        ans += go(i,r) - go(i,l-1);
    }
    return ans;
}
int main(void)
{
    int n;
    ifstream fi("zoo.in");
    ofstream fo("zoo.out");
    ios_base :: sync_with_stdio(0);
    fi>>n;
    for (int i = 1;i <= n;++i) fi>>a[i]>>b[i],v[++cnt_v] = a[i],v[++cnt_v] = b[i];
    sort(v+1,v+1+cnt_v);
    for (int i = 1;i <= n;++i) a[i] = bin(a[i]),b[i] = bin(b[i]),update_len(a[i],b[i]);
    for (int i = 1;i <= cnt_v;++i) s[i] = new int[query_len(i) - query_len(i-1) + 5];
    for (int i = 1;i <= n;++i) update_arb(a[i],b[i]);
    for (int i = 1;i <= cnt_v;++i) sort(s[i]+1,s[i]+1+len[i]);
    int q;
    fi>>q;
    while (q --)
    {
        int x1,x2,y1,y2;
        fi>>x1>>y1>>x2>>y2;
        x1 = bin(x1);y1 = bin(y1);x2 = bin(x2);y2 = bin(y2);
        fo << query_arb(x2,y1,y2) - query_arb(x1-1,y1,y2) << '\n';
    }
    return 0;
}