Cod sursa(job #3193442)

Utilizator AlexSerban21Serban Alexandru AlexSerban21 Data 14 ianuarie 2024 16:41:51
Problema Ograzi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin ("ograzi.in");
ofstream fout ("ograzi.out");
int n,m,x,y,sol,j,i,l,c,aib[1000002];
struct upd
{
    int x,y,val;
};
vector <upd> v;
struct poz
{
    int x,y;
};
poz pct[100001];
void update (int i,int val)
{
    for (; i<=1000001; i+=(i&-i))
        aib[i]+=val;
}
int query (int i)
{
    int sol=0;
    for (; i>0; i-=(i&-i))
        sol+=aib[i];
    return sol;
}
int cmp (upd &a,upd &b)
{
    return a.x<b.x;
}
int cmp1 (poz &a,poz &b)
{
    return a.x<b.x;
}
int main()
{
    ios_base::sync_with_stdio (false);
    fin.tie (0);
    fout.tie (0);
    fin>>n>>m>>l>>c;
    v.reserve (2*n);
    for (i=1; i<=n; i++)
    {
        fin>>x>>y;
        y++;
        v.push_back ({x,y,1});
        v.push_back ({x+l+1,y,-1});
    }
    sort (v.begin (),v.end (),cmp);
    for (i=1; i<=m; i++)
    {
        fin>>pct[i].x>>pct[i].y;
        pct[i].y++;
    }
    sort (pct+1,pct+m+1,cmp1);
    j=0;
    for (i=1; i<=m; i++)
    {
        while (j<v.size ()&&v[j].x<=pct[i].x)
        {
            update (v[j].y,v[j].val);
            j++;
        }
        sol+=((query (pct[i].y)-query (pct[i].y-c-1))>0);
    }
    fout<<sol;
    return 0;
}