Cod sursa(job #2580520)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 13 martie 2020 18:29:20
Problema Walls Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.19 kb
#include <bits/stdc++.h>
#define DIM 100010
using namespace std;

ifstream fin ("walls.in");
ofstream fout ("walls.out");
int aint[4*DIM];
pair <long long, long long> v[DIM];
int h[DIM],w[DIM];
long long sp[DIM];
set <pair<int,int> > s[DIM];
int n,m,i,j,sol,y;
long long x;

void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod] = h[st];
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);
    aint[nod] = max (aint[nod<<1],aint[(nod<<1)|1]);
}
void update (int nod, int st, int dr, int poz, int val){
    if (st == dr){
        aint[nod] =  val;
        return;
    }
    int mid = (st+dr)>>1;
    if (poz <= mid)
        update (nod<<1,st,mid,poz,val);
    else update ((nod<<1)|1,mid+1,dr,poz,val);

    aint[nod] = max (aint[nod<<1],aint[(nod<<1)|1]);
}
int get_poz (int nod, int st, int dr, int poz, int h){

    if (aint[nod] < h)
        return 0;

    if (st == dr)
        return st;

    int mid = (st+dr)>>1;
    int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;

    if (poz > mid){
        int ans = get_poz (fiu_dr,mid+1,dr,poz,h);
        if (ans) /// se gaseste un element cu inaltimea cel putin h in interval
            return ans;
    }
    /// ma duc in stanga
    return get_poz (fiu_st,st,mid,poz,h);

}
void query (int nod, int st, int dr, int x, int y){
    if (x <= st && dr <= y){
        sol = max (sol,aint[nod]);
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        query (nod<<1,st,mid,x,y);
    if (y > mid)
        query ((nod<<1)|1,mid+1,dr,x,y);
}
int main (){

    fin>>n;
    for (i=1;i<=n;i++){
        fin>>w[i]>>h[i];
        sp[i] = sp[i-1] + w[i] + 1;
        if (i > 1)
            v[i].first = v[i-1].second + 2;
        else v[i].first = 1;
        v[i].second = v[i].first + w[i] - 1;

        //fout<<v[i].first<<" "<<v[i].second<<"\n";
    }
    build (1,1,n);

    fin>>m;
    for (;m--;){
        fin>>x>>y;
        int st = 1, dr = n, poz = 0;
        while (st <= dr){
            int mid = (st+dr)>>1;
            if (sp[mid] <= x){
                poz = mid;
                st = mid+1;
            } else dr = mid-1;
        }

        if (poz == 0){
            fout<<"MISS\n";
            continue;
        }

        sol = 0;
        query (1,1,n,1,poz);
        if (sol < y){
            fout<<"MISS\n";
            continue;
        }

        int idx = get_poz(1,1,n,poz,y); /// zidul unde loveste

        int ok = 0;

        set <pair<int,int> > :: iterator it = s[idx].lower_bound (make_pair(y,0));
        if (it != s[idx].end() && it->first == y){ /// inseamna ca am mai lovit pana acum in zidul asta
            int ap = it->second;
            s[idx].erase (it);
            s[idx].insert (make_pair(y,ap+1));
        } else s[idx].insert (make_pair(y,1));

        it = s[idx].lower_bound (make_pair(y,0));

        fout<<"HIT "<<v[idx].second - it->second + 1<<" "<<idx<<" ";

        if (it->second == w[idx]){
            /// am eliminat tot nivelul y;
            update (1,1,n,idx,y-1);
            fout<<"YES\n";
        } else fout<<"NO\n";

    }


    return 0;
}