Cod sursa(job #857570)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 17 ianuarie 2013 23:21:30
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <map>

#define w second

using namespace std;

const int MaxN = 100005;

int N, X[MaxN], H[MaxN], W[MaxN], IT[4 * MaxN];
map<int, int> Blocks[MaxN];

int Search(int Value) {
    int Left = 1, Right = N, Position = 0;
    while (Left <= Right) {
        int Middle = (Left + Right) / 2;
        if (X[Middle] <= Value)
            Left = Middle + 1, Position = Middle;
        else
            Right = Middle - 1;
    }
    return Position;
}

void Update(int Node, int Left, int Right, int Position, int Value) {
    int Middle = (Left + Right) / 2;
    if (Left == Right) {
        IT[Node] = Position;
        return;
    }
    if (Position <= Middle)
        Update(2 * Node, Left, Middle, Position, Value);
    else
        Update(2 * Node + 1, Middle + 1, Right, Position, Value);
    IT[Node] = (H[IT[2 * Node]] > H[IT[2 * Node + 1]] ? IT[2 * Node] : IT[2 * Node + 1]);
}

int Query(int Node, int Left, int Right, int Position, int Value) {
    int Middle = (Left + Right) / 2;
    if (H[IT[Node]] < Value)
        return -1;
    if (Right <= Position && Left == Right)
        return IT[Node];
    int Answer = -1;
    if (Middle < Position && H[IT[2 * Node + 1]] >= Value)
        Answer = Query(2 * Node + 1, Middle + 1, Right, Position, Value);
    if (Answer == -1)
        return Query(2 * Node, Left, Middle, Position, Value);
}

void Solve() {
    assert(freopen("walls.out", "w", stdout));
    int M; assert(scanf("%d", &M) == 1);
    for (; M > 0; --M) {
        int x, y; assert(scanf("%d %d", &x, &y) == 2);
        int Position = Search(x);
        if (Position == 0) {
            printf("MISS\n"); continue;
        }
        Position = Query(1, 1, N, Position, y);
        if (Position == -1) {
            printf("MISS\n"); continue;
        }
        printf("HIT");
        ++Blocks[Position][y];
        map<int, int>::iterator Cell = Blocks[Position].find(y);
        printf(" %d %d", X[Position] - Cell->w + 1, Position);
        if (Cell->w == W[Position]) {
            Blocks[Position].erase(Cell, Blocks[Position].end());
            H[Position] = y - 1; Update(1, 1, N, Position, H[Position]);
            printf(" YES\n");
        } else {
            printf(" NO\n");
        }
    }
}

void Read() {
    assert(freopen("walls.in", "r", stdin));
    assert(scanf("%d", &N) == 1);
    X[0] = -1;
    for (int i = 1; i <= N; ++i) {
        assert(scanf("%d %d", &W[i], &H[i]) == 2);
        X[i] = X[i - 1] + 1 + W[i];
        Update(1, 1, N, i, H[i]);
    }
}

int main() {
    Read();
    Solve();
    return 0;
}