Cod sursa(job #2008167)

Utilizator otto1Palaga Vicentiu-Octavian otto1 Data 5 august 2017 16:45:17
Problema Ograzi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.82 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <time.h>
using namespace std;

#define MAX_Y 50100
#define MAX_N 50100
#define MAX_OI 100100
#define MAXARB 50100

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

int N, M, W, H, K, res, Y[MAX_Y], aib[MAXARB], Ind[MAX_N];
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 r = 0, len;

    for(len = 1; len < K; len<<=1) ;
    for(; len; len>>=1)
     if(r+len <= K && Y[r+len] <= X)
        r += len;
    return r;
}

void preproc(void)
{
    int i, ind;

    for(i = 1; i <= N; i++)
        Y[++K] =  B[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] = getind(B[i].y);
}

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, t2, 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], 1),
            indbagat++;

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

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

        if(r > 0)
            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);

    int start, end;

    start = clock();

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

    end = clock();

//    fprintf(stderr, "%lf\n", (double)(end-start) / CLK_TCK);

    return 0;
}