Cod sursa(job #609449)

Utilizator SpiderManSimoiu Robert SpiderMan Data 21 august 2011 14:14:45
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
# include <cstdio>
# include <ext/hash_map>
using namespace std;
using namespace __gnu_cxx ;

# define x first
# define y second
# define mp make_pair

typedef pair <int, int> PR;
const char *FIN = "walls.in", *FOU = "walls.out";
const int MAX = 100005;

int N, T, ai[MAX << 2];
PR V[MAX];
long long sum[MAX];

namespace __gnu_cxx {
template <> struct hash <PR> {
    size_t operator () (PR val) const {
        return val.x * 229 + val.y * 313;
    }
} ;
}

hash_map <PR, int> H;

void update (int nod, int st, int dr, int poz, int val) {
    if (st == dr) {
        ai[nod] = val;
        return ;
    }
    int mij = st + dr >> 1;
    if (poz <= mij) update (nod << 1, st, mij, poz, val);
    else            update (nod << 1 | 1, mij + 1, dr, poz, val);
    ai[nod] = max (ai[nod << 1], ai[nod << 1 | 1]);
}

int query (int nod, int st, int dr, int li, int ls) {
    if (li < sum[st] || ls > ai[nod]) return 0;
    if (st == dr) return dr;
    int mij = st + dr >> 1;
    int aux = query (nod << 1 | 1, mij + 1, dr, li, ls);
    if (aux == 0) aux = query (nod << 1, st, mij, li, ls);
    return aux;
}

int main (void) {
    freopen (FIN, "r", stdin);
    freopen (FOU, "w", stdout);

    scanf ("%d", &N);
    for (int i = 1; i <= N; ++i) {
        scanf ("%d %d", &V[i].x, &V[i].y);
        update (1, 1, N, i, V[i].y);
        sum[i] = sum[i - 1] + V[i - 1].x + 1;
    }
    for (scanf ("%d", &T); T; --T) {
        int x, y, poz, aux;
        scanf ("%d %d", &x, &y);
        if (poz = query (1, 1, N, x, y)) {
            H[mp (poz, y)] = (H.count (mp (poz, y)) > 0) ? H[mp (poz, y)] + 1 : 1;
            printf ("HIT %d %d ", aux = sum[poz] + V[poz].x - H[mp (poz, y)], poz);
            if (aux == sum[poz]) printf ("YES\n"), update (1, 1, N, poz, y - 1);
            else printf ("NO\n");
        } else {
            printf ("MISS\n");
            continue;
        }
    }
}