Cod sursa(job #2440662)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 18 iulie 2019 22:17:58
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back

using namespace std;

ifstream f("zoo.in");
ofstream g("zoo.out");

typedef long long ll;

int n, q;
pair<int, int> v[16002], poz[16002];
struct rct
{
    int xa, ya;
    int xb, yb;
    int ans;
};
rct qu[102002];
vector<int>aint[80002], a;
void build(int nod, int st, int dr)
{
    if(st == dr)
    {
        aint[nod].pb(v[st].se);
        return;
    }
    int mid = (st + dr) / 2;
    build(nod << 1, st, mid);
    build(nod << 1|1, mid+1, dr);
    aint[nod].resize(aint[2*nod].size()+aint[2*nod+1].size());
    merge(aint[2*nod].begin(), aint[2*nod].end(), aint[2*nod+1].begin(),aint[2*nod+1].end(), aint[nod].begin());
}
int query(int nod, int st, int dr, int L, int R, int s, int d)
{
    if(dr < L || st > R)
        return 0;
    if(L <= st && dr <= R)
        return upper_bound(aint[nod].begin(),aint[nod].end(),d)-lower_bound(aint[nod].begin(),aint[nod].end(),s);
    int mid = (st + dr) / 2;
    return query(nod << 1, st, mid, L, R, s, d) + query(nod << 1|1, mid+1, dr, L, R, s, d);
}
int main()
{
    f >> n;
    for(int i = 1; i <= n; ++i)
        f >> v[i].fi >> v[i].se;
    sort(v+1, v+n+1);
    for(int i = 1; i <= n; ++i)
        a.push_back(v[i].fi);
    build(1, 1, n);
    f >> q;
    for(int i = 1; i <= q; ++i)
    {
        f >> qu[i].xa >> qu[i].ya >> qu[i].xb >> qu[i].yb;
        int poz1, poz2;
        poz1 = lower_bound(a.begin(),a.end(),qu[i].xa)-a.begin();
        poz2 = upper_bound(a.begin(),a.end(),qu[i].xb)-a.begin()-1;
        if(0 <= poz1 && poz2 < n)
            g << query(1, 1, n, poz1+1, poz2+1, qu[i].ya, qu[i].yb) << '\n';
        else
            g << 0 << '\n';
    }
    return 0;
}