Cod sursa(job #25520)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 4 martie 2007 12:49:09
Problema Ograzi Scor 20
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 2.61 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#define NMAX 200200
#define TMAX (1<<20)

using namespace std;

struct panamea
{
        int x, y, cat, ce;
}
        V[NMAX];

int N, M, W, H, K, T[2*TMAX], Sol, A, B;
vector<int> D;

bool operator<(const struct panamea &a, const struct panamea &b)
{
        if ((a.x < b.x) || (a.x == b.x && a.y < b.y) || (a.x == b.x && a.y == b.y && a.ce < b.ce))
           return 1;
        return 0;
}

void update(int p1, int p2, int nod, int val)
{
        int mij;

        if (A <= p1 && p2 <= B)
        {
                T[nod]+=val;
                return;
        }
        if ((p1 <= A && A <= p2) || (p1 <= B && B <= p2))
        {
                mij = (p1+p2)/2;
                update(p1, mij, 2*nod, val);
                update(mij+1, p2, 2*nod+1, val);
        }
}

int query(int x)
{
        int nod = TMAX+x, s = 0;

        s+=T[nod];
        while (nod>1)
        {
                nod/=2;
                s += T[nod];
        }
        return (s>0);
}

int main()
{
        int i, j, a, b, nv = 0;
        char s[101];

        freopen("ograzi.in", "r", stdin);
        scanf("%d %d %d %d ", &N, &M, &W, &H);

        for (i = 0; i < N; i++)
        {
                gets(s);
                b = 0;
                for (j = 0; j < strlen(s); j++)
                    if (s[j] != ' ') b = b*10+(int)(s[j]-'0');
                    else a = b, b = 0;
                D.push_back(H);
                V[nv].x = a; V[nv].y = b; V[nv].cat = i; V[nv++].ce = -1;
                V[nv].x = a+W; V[nv].y = b; V[nv].cat = i; V[nv++].ce = 1;
        }

        for (i = 0; i < M; i++)
        {
                gets(s);
                b = 0;
                for (j = 0; j < strlen(s); j++)
                    if (s[j] != ' ') b = b*10+(int)(s[j]-'0');
                    else a = b, b = 0;
                V[nv].x = a; V[nv].y = b; V[nv].cat = i; V[nv++].ce = 0;
        }

        sort(&V[0], &V[nv]);

        for (i = 0; i < nv; i++)
        {
                if (V[i].ce == -1)
                {
                        A = V[i].y; B = V[i].y + D[ V[i].cat ];
                        update(0, TMAX-1, 1, 1);
                }
                if (V[i].ce == 0)
                   Sol += query(V[i].y);
                if (V[i].ce == 1)
                {
                        A = V[i].y; B = V[i].y + D[ V[i].cat ];
                        update(0, TMAX-1, 1, -1);
                }

        }

        freopen("ograzi.out", "w", stdout);
        printf("%d\n", Sol);

        return 0;
        
}