Cod sursa(job #1938067)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 24 martie 2017 16:37:26
Problema Ograzi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 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> > I[1<<20],E[1<<20];
vector <int> O[1<<20];
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>>m>>n;
    for(i=1;i<=N;++i)
    {
        f>>x>>y;
        I[x].push_back(make_pair(y,y+m));
        E[x+n].push_back(make_pair(y,y+m));
    }
    for(i=1;i<=m;++i)
    {
        f>>x>>y;
        O[x].push_back(y);
    }
    for(i=0;i<=1000000;++i)
    {
        for(j=0;j<I[i].size();++j)
        {
            update(I[i][j].first,1);
            update(I[i][j].second+1,-1);
        }
        for(j=0;j<O[i].size();++j) sol+=query(O[i][j]);
        for(j=0;j<E[i].size();++j)
        {
            update(E[i][j].first,-1);
            update(E[i][j].second+1,1);
        }
    }
    g<<sol;
    return 0;
}