Cod sursa(job #2519270)

Utilizator robx12lnLinca Robert robx12ln Data 7 ianuarie 2020 14:59:27
Problema Walls Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("walls.in");
ofstream fout("walls.out");

const int DIM = 1e5 + 5;

int N, M;
int w[DIM], h[DIM], posx[DIM], A[4 * DIM];
map< int, int > cnt[DIM]; // cate blocuri am distrus pe randul de la inaltimea key al zidului i

inline int caut_bin( int x ){
    int st = 1, dr = N, mid;
    while( st <= dr ){
        mid = ( st + dr ) >> 1;
        if( posx[mid] < x )
            st = mid + 1;
        else
            dr = mid - 1;
    }
    return dr;
}

void upd( int nod, int st, int dr, int pos ){
    int Nst = ((nod<<1)^0);
    int Ndr = ((nod<<1)|1);
    if( st == dr ){
        A[nod] = st;
    }else{
        int mid = ( st + dr ) >> 1;
        if( pos <= mid )
            upd( Nst, st, mid + 0, pos );
        else
            upd( Ndr, mid + 1, dr, pos );
        if( h[ A[Nst] ] >= h[ A[Ndr] ] )
            A[nod] = A[Nst];
        else
            A[nod] = A[Ndr];
    }
}

int query( int nod, int st, int dr, int pos, int val ){ // cea mai la dreapta pozitie ai h[pozitie] >= val
    if( h[ A[nod] ] < val )
        return -1;
    int Nst = ((nod<<1)^0);
    int Ndr = ((nod<<1)|1);
    if( st == dr )
        return st;
    else{
        int mid = ( st + dr ) >> 1;
        if( pos <= mid ){
            return query( Nst, st, mid + 0, pos, val );
        }else{
            int r = query( Ndr, mid + 1, dr, pos, val );
            if( r == -1 )
                r = query( Nst, st, mid + 0, pos, val );
            return r;
        }
    }
}

int main(){

    fin >> N;
    for( int i = 1; i <= N; i++ ) {
        fin >> w[i] >> h[i];
        upd( 1, 1, N, i );
    }

    posx[1] = 1;
    for( int i = 2; i <= N; i++ )
        posx[i] = posx[i - 1] + w[i - 1] + 1;

    fin >> M;
    for( int i = 1; i <= M; i++ ){
        int x, y; fin >> x >> y;
        x = caut_bin( x );
        x = query( 1, 1, N, x, y );
        if( x == -1 ){
            fout << "MISS\n";
            continue;
        }
        fout << "HIT ";
        if( cnt[x].find( y ) == cnt[x].end() )
            cnt[x][y] = 0;
        fout << posx[x] + w[x] - cnt[x][y] - 1 << " " << x << " ";
        cnt[x][y]++;
        if( cnt[x][y] == w[x] )
            fout << "YES\n";
        else
            fout << "NO\n";

        if( cnt[x][y] == w[x] ){
            h[x] = max( 0, y - 1 );
            upd( 1, 1, N, x );
        }
    }

    return 0;
}