Cod sursa(job #2909740)

Utilizator Savu_Stefan_CatalinSavu Stefan Catalin Savu_Stefan_Catalin Data 15 iunie 2022 11:14:31
Problema Zoo Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <fstream>
#include <map>
#include <algorithm>
using namespace std;
ifstream in("zoo.in");
ofstream out("zoo.out");
int n,i,cnt,m,ok,vv;
map<int,int> ma,ar[100005];
pair<int,int> p[100005],val[200005];
pair<pair<int,int>,pair<int,int> > s[100005];
void upd1(int x,int y,int val)
{
    for (int i=x;i<=cnt;i+=(i&(-i)))
        for (int j=y;j<=cnt;j+=(j&(-j)))
    ar[i][j]+=val;
}
int que(int x,int y)
{
    int sum=0;
    for (int i=x;i>0;i-=(i&(-i)))
        for (int j=y;j>0;j-=(j&(-j)))
        sum+=ar[i][j];
    return sum;
}
int main()
{
    in>>n;
    for (i=1;i<=n;++i)
    {
        in>>p[i].first>>p[i].second;
        val[++val[0].first].first=p[i].first;
        val[val[0].first].second=1;
        val[++val[0].first].first=p[i].second;
        val[val[0].first].second=1;
    }
    in>>m;
    for (i=1;i<=m;++i)
    {
        in>>s[i].first.first>>s[i].first.second>>s[i].second.first>>s[i].second.second;
        val[++val[0].first].first=s[i].first.first;
        val[++val[0].first].first=s[i].second.first;
        val[++val[0].first].first=s[i].first.second;
        val[++val[0].first].first=s[i].second.second;
    }
    sort(val+1,val+val[0].first+1);
    cnt=1;
    for (i=1;i<=val[0].first;)
    {
        ok=0;
        cnt++;
        while (ok==0&&i<=val[0].first){
        vv=val[i].first;
        ma[vv]=cnt;
        while (vv==val[i].first) {ok=((ok)|(val[i].second)); i++;}
        }
    }
    for (i=1;i<=n;++i)
    {
        p[i].first=ma[p[i].first];
        p[i].second=ma[p[i].second];
    }
    for (i=1;i<=m;++i)
    {
        s[i].first.first=ma[s[i].first.first];
        s[i].first.second=ma[s[i].first.second];
        s[i].second.first=ma[s[i].second.first];
        s[i].second.second=ma[s[i].second.second];
    }
    for (i=1;i<=n;++i)
    {
        upd1(p[i].first,p[i].second,1);
    }
    for (i=1;i<=m;++i)
    {
        out<<que(s[i].second.first,s[i].second.second)+que(s[i].first.first-1,s[i].first.second-1)-que(s[i].second.first,s[i].first.second-1)-que(s[i].first.first-1,s[i].second.second);
        out<<'\n';
    }
    return 0;
}