Cod sursa(job #1196571)

Utilizator florin.elfusFlorin Elfus florin.elfus Data 8 iunie 2014 14:36:59
Problema Gropi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

struct groapa
{
    int x, y;
} x[100100];

inline bool comp(groapa A, groapa B)
{
    return A.y < B.y;
}

int zone[100100], last[100100], cul[100100];

inline int search(int val)
{
    int st = 1, dr = zone[0], med;

    while (st <= dr)
    {
        med = (st + dr) / 2;
        if (zone[med] == val)
            return med;
        if (zone[med] < val)
            st = med + 1;
        else
            dr = med - 1;
    }

    return st;
}

inline void schimba(int &A, int &B)
{
    int aux = A;
    A = B;
    B = aux;
}

inline int changeCol(int col)
{
    if (col == 1)
        return 2;
    return 1;
}

inline int search2(int val, int N)
{
    int st = 1, dr = N, med;

    while (st <= dr)
    {
        med = (st + dr) / 2;
        if (x[med].y < val)
            st = med + 1;
        else
            dr = med - 1;
    }

    return st;
}

inline bool linDreapta(int val1, int val2, int N)
{
    return search2(val1, N) == search2(val2, N);
}

int main()
{
    int C, N, Q, x0, y0, x1, y1, i, sol, zoneX0, zoneX1;

    freopen("gropi.in", "r", stdin);
    freopen("gropi.out", "w", stdout);

    scanf("%d%d", &C, &N);
    for (i = 1; i <= N; i ++)
        scanf("%d%d", &x[i].x, &x[i].y);

    sort(x + 1, x + N + 1, comp);

    x[0].x = changeCol(x[1].x);
    x[N + 1].x = changeCol(x[N].x); x[N + 1].y = C + 1;
    for (i = 1; i <= N + 1; i ++)
        if (x[i].x != x[i - 1].x)
        {
            zone[++ zone[0]] = x[i].y - 1;
            cul[zone[0]] = x[i - 1].x;
            last[zone[0]] = x[i - 1].y;
        }

    scanf("%d", &Q);
    while (Q --)
    {
        scanf("%d%d%d%d", &x0, &y0, &x1, &y1);
        if (y0 > y1)
        {
            schimba(x0, x1);
            schimba(y0, y1);
        }

        sol = y1 - y0 + 1;
        zoneX0 = search(y0);
        zoneX1 = search(y1);

        if (zoneX0 == zoneX1 && linDreapta(y0, y1, N))
        {
            if (x0 != x1)
                sol ++;
            printf("%d\n", sol);
            continue;
        }
        if (y0 < last[zoneX0] && x0 == cul[zoneX0])
            sol ++;
        if (x1 == cul[zoneX1])
            sol ++;
        sol += zoneX1 - zoneX0;
        if (zoneX0 < zoneX1 && y0 >= last[zoneX0] && x0 == cul[zoneX0])
            sol --;

        printf("%d\n", sol);
    }

    return 0;
}