Cod sursa(job #1000946)

Utilizator poptibiPop Tiberiu poptibi Data 23 septembrie 2013 23:40:54
Problema Ograzi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cctype>
using namespace std;

const int NMAX = 200010, COORDMAX = 1000010, MAXB = 1000000;

int N, M, W, H, X, Y, FT[COORDMAX], K, Sol;

struct Events 
{
    int X, Priority, Y;
}E[NMAX];

char Buf[MAXB];
int Ptr;

struct Comp 
{
    bool operator() (const Events &A, const Events &B) const 
    {
        if(A.X != B.X) return A.X < B.X;
        if(A.Priority != B.Priority) return A.Priority < B.Priority;
        return A.Y < B.Y;
    }
};

int LSB(int X)
{
    return (X & (X - 1)) ^ X;
}

void Update(int Pos, int Val)
{
    for(; Pos < COORDMAX; Pos += LSB(Pos))
        FT[Pos] += Val;
}

int Ask(int Pos)
{
    int Ans = 0;
    for(; Pos > 0; Pos -= LSB(Pos))
        Ans += FT[Pos];
    return Ans;
}

int GetInt()
{
    int Ans = 0;
    while(!isdigit(Buf[Ptr]))
        if(++ Ptr >= MAXB)
            fread(Buf, 1, MAXB, stdin), Ptr = 0;
    while(isdigit(Buf[Ptr]))
    {
        Ans = Ans * 10 + Buf[Ptr] - '0';
        if(++ Ptr >= MAXB)
            fread(Buf, 1, MAXB, stdin), Ptr = 0;
    }
    return Ans;
}

int main()
{
    freopen("ograzi.in", "r", stdin);
    freopen("ograzi.out", "w", stdout);
    fread(Buf, 1, MAXB, stdin);
    
    N = GetInt();
    M = GetInt();
    W = GetInt();
    H = GetInt();
    for(int i = 1; i <= N; ++ i)
    {
        X = GetInt();
        Y = GetInt();
        X ++;
        Y ++;
        
        E[++ K].X = X;
        E[K].Priority = 1;
        E[K].Y = Y;
        
        E[++ K].X = X + W;
        E[K].Priority = 3;
        E[K].Y = Y;
    }
    
    for(int i = 1; i <= M; ++ i)
    {
        X = GetInt();
        Y = GetInt();
        X ++;
        Y ++;
        
        E[++ K].X = X;
        E[K].Priority = 2;
        E[K].Y = Y;
    }
    
    sort(E + 1, E + K + 1, Comp());
    
    for(int i = 1; i <= K; ++ i)
    {
        if(E[i].Priority == 1) Update(E[i].Y, 1);
        else if(E[i].Priority == 2)
        {
            if(Ask(E[i].Y) > Ask(E[i].Y - H - 1))
                Sol ++;
        }else Update(E[i].Y, -1);
    }
    
    printf("%i\n", Sol);
    
    return 0;
}