Cod sursa(job #1938095)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 24 martie 2017 16:52:34
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("ograzi.in");
ofstream g("ograzi.out");
int N,M,m,n,i,j,x,y,sol,aib[1<<20];
vector <pair <int,int> > O;
struct pt
{
    int x;
    int y;
    int Y;
}I[1<<16],E[1<<16];
bool cmp(pt a,pt b)
{
    return a.x<b.x;
}
void update(int x,int val)
{
    for(;x<=1000000;x+=(x&(-x))) aib[x]+=val;
}
bool query(int x)
{
    int nr=0;
    for(;x;x-=(x&(-x))) nr+=aib[x];
    return nr>0;
}
int main()
{
    f>>N>>M>>n>>m;
    for(i=1;i<=N;++i)
    {
        f>>x>>y;
        I[i]={x,y,y+m};
        E[i]={x+n,y,y+m};
    }
    for(i=1;i<=m;++i)
    {
        f>>x>>y;
        O.push_back(make_pair(x,y));
    }
    sort(I+1,I+N+1,cmp);
    sort(E+1,E+N+1,cmp);
    sort(O.begin(),O.end());
    int ins=1,ers=1,ver=0;
    for(i=0;i<=1000000;++i)
    {
        for(;I[ins].x==i&&ins<=N;++ins)
        {
            update(I[ins].y,1);
            update(I[ins].Y+1,-1);
        }
        for(;ver<O.size();++ver)
            if(O[ver].first==i) sol+=query(O[ver].second);
            else break;
        for(;E[ers].x==i&&ers<=N;++ers)
        {
            update(E[ers].y,-1);
            update(E[ers].Y+1,1);
        }
    }
    g<<sol;
    return 0;
}