Cod sursa(job #2964177)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 12 ianuarie 2023 16:04:21
Problema Zoo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;
ifstream cin("zoo.in");
ofstream cout("zoo.out");
const int N = 16007,Inf = 2*1e9 + 3;
int a,b,n,x1,x2,y1,y2,q;
using PI = pair<int,int>;
vector<PI> v,aux;
vector<int> auxx,auxy;
int aib[N][N];

// O(log2(n) * log2(n))
int query(int i, int j) // face suma submatricei (1, 1) -> (i, j)
{
	int suma = 0;
	for (int x = i; x; x -= x & -x)
		for (int y = j; y; y -= y & -y)
		suma += aib[x][y];

	return suma;
}

void update(int i, int j, int v) // adaug v la a[i][j]
{
	for (int x = i; x < N; x += x & -x)
		for (int y = j; y < N; y += y & -y)
			aib[x][y] += v;
}
int query(int x1,int y1,int x2,int y2)
{
    return query(x2,y2) -  query(x2,y1-1) - query(x1-1,y2) + query(x1-1,y1-1);
}

int main()
{
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>a>>b;
        v.emplace_back(a,b);
    }
    for(int i=0;i<n;++i)
        auxx.push_back(v[i].first),
        auxy.push_back(v[i].second);

    vector<tuple<int,int,int,int> >queris;
    cin>>q;
    while(q--)
    {
        cin>>x1>>y1>>x2>>y2;
        queris.emplace_back(x1,y1,x2,y2);
        auxx.push_back(x1);
        auxx.push_back(x2);
        auxy.push_back(y1);
        auxy.push_back(y2);
    }

    sort(auxx.begin(),auxx.end());
    auxx.erase(unique(auxx.begin(),auxx.end()),auxx.end());
    sort(auxy.begin(),auxy.end());
    auxy.erase(unique(auxy.begin(),auxy.end()),auxy.end());

    for(int i=0;i<n;++i)
    {
        int px = lower_bound(auxx.begin(),auxx.end(),v[i].first) - auxx.begin() + 1;
        int py = lower_bound(auxy.begin(),auxy.end(),v[i].second) - auxy.begin() + 1;
        update(px,py,1);
    }

    for(auto i : queris)
    {
        int x1 = lower_bound(auxx.begin(),auxx.end(),get<0>(i)) - auxx.begin() + 1;
        int y1 = lower_bound(auxx.begin(),auxx.end(),get<1>(i)) - auxx.begin() + 1;
        int x2 = lower_bound(auxy.begin(),auxy.end(),get<2>(i)) - auxy.begin() + 1;
        int y2 = lower_bound(auxy.begin(),auxy.end(),get<3>(i)) - auxy.begin() + 1;
        cout<<query(x1,y1,x2,y2)<<'\n';
    }
    return 0;
}