Cod sursa(job #3254297)

Utilizator andiRTanasescu Andrei-Rares andiR Data 7 noiembrie 2024 00:30:50
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.69 kb
// Author: Tanasescu Andrei-Rares
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>
#include <cassert>

#pragma GCC optimize("O3")

#define fi first
#define se second
#define pb push_back
#define pf push_front

using namespace std;

ifstream fin ("zoo.in");
ofstream fout ("zoo.out");

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll Nmax=16e3+5, Mmax=1e5+5, Vmax=Nmax+Mmax*2, inf=2e9;

int n, m;
vector<int> nx, ny;

pii v[Nmax];

struct event{
    int x, y1, y2;
    int sgn, ind;
}ev[Mmax*2];
bool cmp(event a, event b){
    return a.x<b.x;
}

int sol[Mmax];

struct AIB{
    int v[Vmax];

    inline void add(int pos){
        while (pos<Vmax){
            v[pos]++;
            pos+=pos&-pos;
        }
    }

    inline int _sum(int pos){
        int s=0;
        while (pos>0){
            s+=v[pos];
            pos-=pos&-pos;
        }
        return s;
    }
    inline int sum(int l, int r){
        return _sum(r)-_sum(l-1);
    }
}aib;

int main()
{
    // read animals
    fin>>n;
    for (int i=0; i<n; i++){
        fin>>v[i].fi>>v[i].se;
        nx.pb(v[i].fi);
        ny.pb(v[i].se);
    }
    
    // read farms and add them as events
    fin>>m;
    for (int i=0; i<m; i++){
        int x1, y1, x2, y2;
        fin>>x1>>y1;
        fin>>x2>>y2;

        nx.pb(x1); nx.pb(x2);
        ny.pb(y1); ny.pb(y2);

        ev[i*2]={x1, y1, y2, -1, i};
        ev[i*2+1]={x2, y1, y2, 1, i};
    }

    // normalise
    nx.pb(-inf-1); // 1-indexed
    ny.pb(-inf-1);

    sort(nx.begin(), nx.end());
    sort(ny.begin(), ny.end());
    
    for (int i=0; i<n; i++){
        v[i].fi=lower_bound(nx.begin(), nx.end(), v[i].fi)-nx.begin();
        v[i].se=lower_bound(ny.begin(), ny.end(), v[i].se)-ny.begin();
    }
    sort(v, v+n);

    for (int i=0; i<m*2; i++){
        if (i%2==0)
            ev[i].x=lower_bound(nx.begin(), nx.end(), ev[i].x)-nx.begin()-1;
        else ev[i].x=lower_bound(nx.begin(), nx.end(), ev[i].x)-nx.begin();
        
        ev[i].y1=lower_bound(ny.begin(), ny.end(), ev[i].y1)-ny.begin();
        ev[i].y2=lower_bound(ny.begin(), ny.end(), ev[i].y2)-ny.begin();
    }
    sort(ev, ev+m*2, cmp);
    
    // solve
    int indv=0, indq=0;
    for (int i=0; i<nx.size(); i++){
        while (indv!=n && v[indv].fi==i)
            aib.add(v[indv++].se);
        
        while(indq!=m*2 && ev[indq].x==i)
            sol[ev[indq++].ind]+=ev[indq].sgn*aib.sum(ev[indq].y1, ev[indq].y2);
    }

    // print answers
    for (int i=0; i<m; i++)
        fout<<sol[i]<<'\n';

    return 0;
}