Cod sursa(job #1774098)

Utilizator akaprosAna Kapros akapros Data 8 octombrie 2016 15:58:43
Problema Walls Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <bits/stdc++.h>
#define pii pair < int, int >
#define mp make_pair
#define maxN 100002
using namespace std;
int n, m, q, w[maxN], h[maxN], st[4 * maxN];
ll sum[maxN];
map < pii, int > v;

int bs(int x)
{
    int i = 0, p = 1 << 17;
    while (p)
    {
        if (i + p <= n && sum[i + p] <= 1LL * x)
            i += p;
        p >>= 1;
    }
    return i;
}

void update(int nod, int l, int r, int y, int H)
{
    if (l > r || l > y)
        return ;
    if (l == r)
    {
        st[nod] = y;
        return ;
    }
    int lson = 2 * nod, rson = lson + 1,
        mid = (l + r) >> 1;
    if (mid >= y)
        update(lson, l, mid, y, H);
    else
        update(rson, mid + 1, r, y, H);
    if (h[st[lson]] > h[st[rson]])
        st[nod] = st[lson];
    else
        st[nod] = st[rson];
}
int query(int nod, int l, int r, int x, int y)
{
    if (l > x || l > r)
        return 0;
    if (r <= x)
    {
        if (h[st[nod]] < y)
            return 0;
        if (l == r)
            return st[nod];
    }

    int lson = 2 * nod, rson = lson + 1,
        mid = (l + r) >> 1;
    int ans = query(rson, mid + 1, r, x, y);
    if (ans < 1)
        return query(lson, l, mid, x, y);
    return ans;
}

void read()
{
    freopen("walls.in", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i)
    {
        scanf("%d %d", &w[i], &h[i]);
        sum[i] = sum[i - 1] + 1LL * w[i] + 1LL;
        update(1, 1, n, i, h[i]);
    }
}

void write()
{
    freopen("walls.out", "w", stdout);
    scanf("%d", &q);
    while (q --)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        x = bs(x);
        x = query(1, 1, n, x, y);
        if (x <= 0)
        {
            printf("MISS\n");
            continue;
        }
        int sub = ++ v[mp(x, y)];
        printf("HIT %d %d ", sum[x] - sub, x);
        if (sub == w[x])
        {
            -- h[x];
            update(1, 1, n, x, h[x]);
            printf("YES\n");
        }
        else
            printf("NO\n");
    }
}
int main()
{
    read();
    //solve();
    write();
    return 0;
}