Cod sursa(job #2496151)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 20 noiembrie 2019 11:59:37
Problema Ograzi Scor 0
Compilator cpp-64 Status done
Runda casiaiziscanudaisimulareprimaora Marime 1.45 kb
#include <fstream>
#include <algorithm>
using namespace std;
int n,m,wt,h,maxi,i,j,l,k,p,u,s,aint[20][100005];
struct vec{int a,b;}v[100005],w[100005];
bool comp(vec A, vec B)
{
    return A.b<B.b;
}
void add(int poz, int val)
{
    int hh=0;
    while(hh<=k)
    {
        aint[hh][poz]+=val;
        hh++;
        poz=(poz+1)/2;
    }
}
int sum(int poz)
{
    int hh=0,su=aint[0][poz];
    while(hh<=k)
    {
        if(poz%2==0) su+=aint[hh][poz-1];
        poz=(poz+1)/2;
        hh++;
    }
    return su;
}
int main()
{
    ifstream f("ograzi.in");
    ofstream g("ograzi.out");
    f>>n>>m>>wt>>h;
    for(i=1; i<=n; i++)
    {
        f>>v[i].a>>v[i].b;
        maxi=max(maxi,v[i].b+h+1);
    }
    for(i=1; i<=m; i++)
    {
        f>>w[i].a>>w[i].b;
        maxi=max(maxi,w[i].b+h+1);
    }
    l=m+1;
    k=0;
    while(l>1)
    {
        l=(l+1)/2;
        k++;
    }
    sort(v+1, v+n+1, comp);
    sort(w+1, w+m+1, comp);
    p=1;
    u=0;
    j=0;
    for(i=0; i<=maxi; i++)
    {
        while(u+1<=n&&v[u+1].b==i)
        {
            u++;
            add(v[u].a,1);
            add(v[u].a+wt+1,-1);
        }
        while(p<=n&&v[p].b+h==i-1)
        {
            add(v[p].a,-1);
            add(v[p].a+wt+1,1);
            p++;
        }
        while(j+1<=m&&w[j+1].b==i)
        {
            s+=sum(w[j+1].a);
            j++;
        }
    }
    g<<s<<'\n';
    return 0;
}