Cod sursa(job #850364)

Utilizator stoicatheoFlirk Navok stoicatheo Data 8 ianuarie 2013 13:24:13
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 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 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;
LL bz[NMAX], lg[NMAX];//le fac LL
int h[4*NMAX];
LL T;
int H;
 
void update(int st, int dr, int nod)
{
    if(st == dr)
    {
        h[nod] = H;
        return;
    }
     
    int mij = (st + dr) / 2;
    if(T <= mij) update(st, mij, 2*nod);
    else            update(mij + 1, dr, 2*nod + 1);
    h[nod] = max(h[2*nod], h[2*nod + 1]);
}
 
int query(int st, int dr, int nod)
{
    if(h[nod] < H || bz[st] > T)  return -1;
    if(st == dr)    return st;
     
    int mij = (st + dr) / 2;
    int a = query(mij + 1, dr, 2*nod + 1);
    if(a == -1) a = query(st, mij, 2*nod);
    return a;
}
 
void citi()
{
    scanf("%d", &N);
    int st = 1LL;
    FOR(i, 1, N)
    {
        LL x;
        int y;
        scanf("%lld%d", &x, &y);
        bz[i] = st;
        lg[i] = x;
        st += x + 1;
        T = i;H = y;
        update(1, N, 1);
    }
    scanf("%d", &M);
}
 
void rezolva()
{
    map<PII, int> Hit;//[NMAX];
    FOR(i, 1, M)
    {
        scanf("%lld%d", &T, &H);
        int ind = query(1, N, 1);
        if(ind == -1)
        {
            printf("MISS\n");
            continue;
        }
        int &nr = Hit[mp(ind, H)];
        nr++;
        printf("HIT %lld %d ", bz[ind] + lg[ind] - nr, ind);
        if(nr == lg[ind])
        {
            printf("YES\n");
            H--;
            T = ind;
            update(1, N, 1);
        }
        else    printf("NO\n");
    }
}
 
int main()
{
    freopen(IN, "r", stdin);
    freopen(OUT, "w", stdout);
    citi();
    rezolva();
    return 0;
}