Cod sursa(job #2964174)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 12 ianuarie 2023 15:58:48
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];
void update(int x,int y)
{
    int i,j;
    for(i = x;i<N;i += i&-i)
        for(j= y;j<N;j += j&-j)
            aib[i][j]++;
}
int query(int x,int y) ///returneaza nr de puncte in drept cu colt drepata sus in x,y
{
    int sum = 0;
    int i,j;
    for(i = x;i;i -= i&-i)
        for(j= y;j;j -= j&-j)
            sum+=aib[i][j];
    return sum;
}
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);
    }

    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;
}