Cod sursa(job #3254291)

Utilizator andiRTanasescu Andrei-Rares andiR Data 7 noiembrie 2024 00:11:01
Problema Zoo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.55 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;
map<int, 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()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // read animals
    fin>>n;
    for (int i=0; i<n; i++){
        fin>>v[i].fi>>v[i].se;
        nx[v[i].fi]=0;
        ny[v[i].se]=0;
    }
    
    // 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[x1]=0; nx[x2]=0;
        ny[y1]=0; ny[y2]=0;

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

    // normalise
    nx[-inf-1]=0; // 1-indexed
    ny[-inf-1]=0;

    int i=0;
    for (auto it:nx)
        nx[it.fi]=i++;
    i=0;
    for (auto it:ny)
        ny[it.fi]=i++;
    
    for (int i=0; i<n; i++){
        v[i].fi=nx[v[i].fi];
        v[i].se=ny[v[i].se];
    }
    sort(v, v+n);

    for (int i=0; i<m*2; i++){
        if (i%2==0)
            ev[i].x=nx[ev[i].x]-1;
        else ev[i].x=nx[ev[i].x];
        
        ev[i].y1=ny[ev[i].y1];
        ev[i].y2=ny[ev[i].y2];
    }
    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;
}