Cod sursa(job #548452)

Utilizator ooctavTuchila Octavian ooctav Data 7 martie 2011 14:28:46
Problema Walls Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.18 kb
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<vector>
using namespace std;

const char IN[] = {"walls.in"};
const char OUT[] = {"walls.out"};
const int INF = 1000000005;
const double PI  = 3.14159265;
const int NMAX = 100005;

#define II inline
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define PDD pair<double, double>
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define FOR(i, a, b)     for(int i = a ; i <= b ; i++)
#define IFOR(i, a, b)     for(int i = a ; i >= b ; i--)
#define FORIT(it, V)     for(vector<int> :: iterator it = V.begin() ; it != V.end() ; it++)
#define all(a) a, a +

int N, M;
PLL baza[NMAX];
LL X, Y;
LL Adi[8 * NMAX];
set<PLL> S[NMAX];

void update(int st, int dr, int nod)
{
    if(st == dr)
    {
        Adi[nod] = Y;
        return;
    }
   
    int mij = (st + dr) / 2;
    if(X <= mij)    update(st, mij, 2*nod);
    else            update(mij + 1, dr, 2*nod + 1);
   
    Adi[nod] = max(Adi[2*nod], Adi[2*nod + 1]);
}

PLL query(int st, int dr, int nod)
{
	if(X < st)	return mp(0, 0);
    if(st == dr)
        return mp((LL)st, Adi[nod]);
   
    int mij = (st + dr) / 2;
	
	if(X < dr)
	{	
		PLL a, b;
		a = query(st, mij, 2*nod);		
		b = query(mij + 1, dr, 2*nod + 1);
		if(b.sc >= Y)	return b;
		else			return a;
	}
    if(Adi[2*nod + 1] < Y)    return query(st, mij, 2*nod);
    else                      return query(mij + 1, dr, 2*nod + 1);
}

void citi()
{
    scanf("%d", &N);
    baza[0].sc = -1;
    FOR(i, 1, N)
    {
        LL w, h;
        scanf("%lld%lld", &w, &h);
        baza[i].fs = baza[i - 1].sc + 2;
        baza[i].sc = baza[i].fs + w - 1;
        X = i; Y = h;
        update(1, N, 1);
    }
}

int caut_bin(LL x)
{
    int REZ = 0, pas;
    for(pas = 1 ; pas < N ; pas <<= 1);
    for( ; pas ; pas >>= 1)
        if(REZ + pas <= N && baza[REZ + pas].sc < x)
            REZ += pas;
    return REZ;
}

void apel()
{
    scanf("%d", &M);
    FOR(i, 1, M)
    {
        LL x, y;// fac long long
        scanf("%lld%lld", &x, &y);//fac lld
       
        X = caut_bin(x);
        Y = y;
        PLL k = query(1, N, 1);
        if((!k.fs && !k.sc) || (k.fs == 1 && (LL)k.sc < y))
            printf("MISS\n");
        else
        {
            set<PLL> :: iterator it;
            LL scot = 1;
            if(S[k.fs].size())
            {
                it = S[k.fs].lower_bound(mp(y, 0));
                if(it != S[k.fs].end())
                {
                    scot += it->sc;
                    S[k.fs].erase(it);
                }
                S[k.fs].insert(mp(k.fs, scot));
            }
            S[k.fs].insert(mp(y, scot));
			
            printf("HIT %lld ", baza[k.fs].sc - scot + 1);
			printf("%lld ", k.fs);
            if(baza[k.fs].sc - baza[k.fs].fs + 1 == scot)
            {
                printf("YES\n");
                X = k.fs;
                Y = y - 1;
                update(1, N, 1);
            }
            else
                printf("NO\n");
        }
    }
}

int main()
{
    freopen(IN, "r", stdin);
    freopen(OUT, "w", stdout);
    citi();
    apel();
    return 0;
}