Cod sursa(job #25173)

Utilizator astronomyAirinei Adrian astronomy Data 4 martie 2007 11:14:10
Problema Ograzi Scor 70
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 2.95 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define MAX_Y 200200
#define MAX_N 50010
#define MAX_OI 100020
#define MAXARB 200200

typedef struct point { int x, y; } point;

int N, M, W, H, K, res, Y[MAX_Y], aib[MAXARB], Ind[MAX_N][2];
point A[MAX_OI], B[MAX_N];

int cmp(point a, point b)
{
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

int getind(int X)
{
    int st = 1, dr = K, m, r = 0;

    while(st <= dr)
    {
        m = (st+dr) >> 1;
        if( Y[m] <= X )
            r = m, st = m+1;
        else
            dr = m-1;
    }

    return r;
}

void preproc(void)
{
    int i, ind;

    for(i = 1; i <= N; i++)
        Y[++K] =  B[i].y, Y[++K] = B[i].y+H;
    for(i = 1; i <= M; i++)
        Y[++K] = A[i].y;

    sort(Y+1, Y+K+1);

    for(ind = 1, i = 2; i <= K; i++)
     if(Y[i] != Y[ind])
        Y[++ind] = Y[i];

    K = ind;

    sort(B+1, B+N+1, cmp);
    sort(A+1, A+M+1, cmp);
    
    for(i = 1; i <= N; i++)
        Ind[i][0] = getind(B[i].y), Ind[i][1] = getind(B[i].y+H);
}

void update(int x, int val)
{
    for(; x <= K; x += (x&(x-1))^x)
        aib[x] += val;
}

int query(int x)
{
    int val = 0;
    for(; x > 0; x -= (x&(x-1))^x)
        val += aib[x];
    return val;
}

void solve(void)
{
    int i, t, r, p, indbagat = 1, indscos = 1, x, y;

    preproc();
    
    for(i = 1; i <= M; i++)
    {
        x = A[i].x, y = A[i].y;
        
        while(indbagat <= N && B[indbagat].x <= x)
            update(Ind[indbagat][0], 1),
            update(Ind[indbagat][1], 1),
            indbagat++;

        while(indscos <= N && B[indscos].x+W < x)
            update(Ind[indscos][0], -1),
            update(Ind[indscos][1], -1),
            indscos++;

        t = getind(y), r = query(t), p = query(t-1);

        if( (r & 1) || (r-p == 1) )
            res++;
    }
}

void read_data(void)
{
    int i, x, y, j, ind;
    char sir[1024];

    scanf("%d %d %d %d\n", &N, &M, &W, &H);

    for(i = 1; i <= N; i++)
    {
        fgets(sir, 1024, stdin), ind = x = y = 0;
        for(; sir[ind] >= '0' && sir[ind] <= '9'; ind++)
            x = x*10+(sir[ind]-48);
        for(ind++; sir[ind] >= '0' && sir[ind] <= '9'; ind++)
            y = y*10+(sir[ind]-48);
        B[i].x = x, B[i].y = y;
    }
    for(i = 1; i <= M; i++)
    {
        fgets(sir, 1024, stdin), ind = x = y = 0;
        for(; sir[ind] >= '0' && sir[ind] <= '9'; ind++)
            x = x*10+(sir[ind]-48);
        for(ind++; sir[ind] >= '0' && sir[ind] <= '9'; ind++)
            y = y*10+(sir[ind]-48);
        A[i].x = x, A[i].y = y;
    }
}

void write_data(void)
{
    printf("%d\n", res);
}

int main(void)
{
    freopen("ograzi.in", "rt", stdin);
    freopen("ograzi.out", "wt", stdout);

    read_data();
    solve();
    write_data();

    return 0;
}