Cod sursa(job #2440646)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 18 iulie 2019 21:50:23
Problema Zoo Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.4 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];
short mat[5002][5002];
set<int>sx, sy;
int vx[5002], vy[5002];
int L, C;
int cbx(int val)
{
    int st = 1;
    int dr = L;
    int ans = 0;
    while(st <= dr)
    {
        int mid = (st + dr) / 2;
        if(vx[mid] <= val)
            ans = mid, st = mid + 1;
        else
            dr = mid - 1;
    }
    return ans;
}
int cby(int val)
{
    int st = 1;
    int dr = C;
    int ans = 0;
    while(st <= dr)
    {
        int mid = (st + dr) / 2;
        if(vy[mid] <= val)
            ans = mid, st = mid + 1;
        else
            dr = mid - 1;
    }
    return ans;
}
int sum(int xa, int ya, int xb, int yb)
{
    int ss = mat[xb][yb] - mat[xa][yb] - mat[xb][ya] + mat[xa][ya];
    return ss;
}
void solve(int st, int dr)
{
    sx.clear();
    sy.clear();
    for(int i = st; i <= dr; ++i)
        sx.insert(v[i].fi), sy.insert(v[i].se);
    set<int> ::iterator it;
    L = 0, C = 0;
    for(it = sx.begin(); it != sx.end(); ++it)
        vx[++L] = *it;
    for(it = sy.begin(); it != sy.end(); ++it)
        vy[++C] = *it;
    for(int i = st; i <= dr; ++i)
    {
        poz[i].fi = cbx(v[i].fi);
        poz[i].se = cby(v[i].se);
        mat[poz[i].fi][poz[i].se]++;
    }
    for(int i = 1; i <= L; ++i)
        for(int j = 1; j <= C; ++j)
            mat[i][j] = mat[i][j] + mat[i-1][j] + mat[i][j-1] - mat[i-1][j-1];
    for(int i = 1; i <= q; ++i)
    {
        int aa = cbx(qu[i].xa-1);
        int bb = cby(qu[i].ya-1);
        int cc = cbx(qu[i].xb);
        int dd = cby(qu[i].yb);
        qu[i].ans = qu[i].ans + sum(aa, bb, cc, dd);
    }
    if(dr != n)
        memset(mat, 0, sizeof(mat));
}
int main()
{
    f >> n;
    for(int i = 1; i <= n; ++i)
        f >> v[i].fi >> v[i].se;
    f >> q;
    for(int i = 1; i <= q; ++i)
        f >> qu[i].xa >> qu[i].ya >> qu[i].xb >> qu[i].yb;
    int lst = 0;
    for(int i = 1; i <= n; ++i)
        if(i % 5000 == 0 || i == n)
            solve(lst+1, i), lst = i;
    for(int i = 1; i <= q; ++i)
        g << qu[i].ans << '\n', qu[i].ans = 0;
    return 0;
}