Cod sursa(job #3165961)

Utilizator tudor_costinCostin Tudor tudor_costin Data 7 noiembrie 2023 11:21:51
Problema Zoo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <climits>
#include <set>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
using ll=long long;
const int Nmax=16005;
ll sol[Nmax];
pair<ll,ll> q[Nmax];
pair<ll,ll> a[Nmax];
ll b[Nmax];
multiset<ll> s;
vector<pair<int,bool>> ev[Nmax];
int main()
{
    int n;
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>a[i].first>>a[i].second;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        b[i]=a[i].second;
    }
    int m;
    ll x1,x2,y1,y2;
    fin>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x1>>y1>>x2>>y2;
        pair<ll,ll> lb={x1,LLONG_MIN};
        int poz1=lower_bound(a+1,a+n+1,lb)-a;
        lb={x2,LLONG_MAX};
        int poz2=upper_bound(a+1,a+n+1,lb)-a-1;
        if(poz2<poz1) sol[i]=0;
        else
        {
            q[i]={y1,y2};
            ev[poz1-1].push_back({i,0});
            ev[poz2].push_back({i,1});
        }
    }
    for(int i=1;i<=n;i++)
    {
          s.insert(b[i]);
          for(int j=0;j<ev[i].size();j++)
          {
              int k=ev[i][j].first;
              bool tip=ev[i][j].second;
              auto it1=lower_bound(s.begin(),s.end(),q[k].first);
              auto it2=upper_bound(s.begin(),s.end(),q[k].second);
              int d=distance(it1,it2);
              if(tip==0) sol[k]-=d;
              else sol[k]+=d;
          }
    }
    for(int i=1;i<=m;i++)
    {
        fout<<sol[i]<<'\n';
    }
    return 0;
}