Cod sursa(job #544117)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 1 martie 2011 08:27:07
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <stdio.h>
#include <algorithm>
#include <set>

using namespace std;

#define maxn 100010

int n, m, i, j, k, poz, y;
int w[maxn], h[maxn], arb[3*maxn];
long long x, sp[maxn];
multiset<int> hits[maxn];

void update(int nod, int left, int right, int poz, int val)
{
    if(left==right)
    {
        arb[nod]=val;
        return;
    }
    int med=(left+right)/2;
    if(poz<=med)
        update(nod*2, left, med, poz, val);
    else
        update(nod*2+1, med+1, right, poz, val);
    arb[nod]=max(arb[nod*2], arb[nod*2+1]);
}

int query(int nod, int left, int right, long long limit, int high, int ok)
{
    int med=(left+right)/2;
    if(!ok)
    {
        if(sp[right]<=limit)
        {
            if(arb[nod]>=high)
                return query(nod, left, right, limit, high, 1);
            return 0;
        }
        int sol=0;
        if(sp[med+1]<=limit)
            sol=query(nod*2+1, med+1, right, limit, high, 0);
        if(sol==0)
            sol=query(nod*2, left, med, limit, high, 0);
        return sol;
    }
    if(left==right)
        return left;
    if(arb[nod*2+1]>=high)
        return query(nod*2+1, med+1, right, limit, high, 1);
    return query(nod*2, left, med, limit, high, 1);
}

int main()
{
    freopen("walls.in", "r", stdin);
    freopen("walls.out", "w", stdout);

    scanf("%d", &n);
    for(int i=1; i<=n; ++i)
    {
        scanf("%d%d", &w[i], &h[i]);
        sp[i]=sp[i-1]+w[i-1]+1;
        update(1, 1, n, i, h[i]);
    }

    scanf("%d", &m);
    while(m--)
    {
        scanf("%lld%d", &x, &y);
        poz=query(1, 1, n, x, y, 0);
        if(poz==0)
        {
            printf("MISS\n");
            continue;
        }
        hits[poz].insert(y);
        printf("HIT %lld %d ", sp[poz]+w[poz]-hits[poz].count(y), poz);
        if(hits[poz].count(y)==w[poz])
        {
            h[poz]=y-1;
            update(1, 1, n, poz, h[poz]);
            printf("YES\n");
            continue;
        }
        printf("NO\n");
    }
    return 0;
}