Cod sursa(job #2461804)

Utilizator stefantagaTaga Stefan stefantaga Data 26 septembrie 2019 10:19:49
Problema Walls Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("walls.in");
ofstream g("walls.out");
struct wow
{
    int gr,niv;
}v[100005];
int arb[400005],pozitie,i,st,dr,mij,n,m,s[100005],poz,niv,sol;
map <int,int> mp[100005];
void update (int st,int dr,int nod,int poz,int val)
{
    if (st==dr)
    {
        arb[nod]=val;
        return;
    }
    int mij=(st+dr)/2;
    if (poz<=mij)
    {
        update(st,mij,2*nod,poz,val);
    }
    else
    {
        update(mij+1,dr,2*nod+1,poz,val);
    }
    arb[nod]=max(arb[2*nod],arb[2*nod+1]);
}
int query(int st,int dr,int nod,int valoare)
{
    if (st==dr)
    {
        if (arb[nod]>=valoare)
        {
            pozitie=st;
        }
        return arb[nod];
    }
    int mij=(st+dr)/2;
    int r1=query(mij+1,dr,2*nod+1,valoare);
    int r2=query(st,mij,2*nod,valoare);
    if (r1>=valoare)
    {
        query(mij+1,dr,2*nod+1,valoare);
    }
    else
    if (r2>=valoare)
    {
        query(mij+1,dr,2*nod+1,valoare);
    }
    return max(r1,r2);
}
int main()
{
    f>>n;
    for (i=1;i<=n;i++)
    {
        f>>v[i].gr>>v[i].niv;
        update(1,n,1,i,v[i].niv);
        s[i]=s[i-1]+v[i-1].gr+1;
    }
    f>>m;
    for (i=1;i<=m;i++)
    {
        f>>poz>>niv;
        st=1;
        dr=n;
        while (st<=dr)
        {
            mij=(st+dr)/2;
            if (s[mij]<=poz)
            {
                sol=mij;
                st=mij+1;
            }
            else
            {
                dr=mij-1;
            }
        }
        pozitie=-1;
        query(1,sol,1,niv);
        if (pozitie==-1)
        {
            g<<"MISS"<<'\n';
        }
        else
        {
            g<<"HIT"<<" ";
            g<<s[pozitie]+v[pozitie].gr-1-mp[pozitie][niv]<<" "<<pozitie<<" ";
            mp[pozitie][niv]++;
            if (mp[pozitie][niv]==v[pozitie].gr)
            {
                update(1,n,1,pozitie,niv-1);
                g<<"YES"<<'\n';
            }
            else
            {
                g<<"NO"<<'\n';
            }
        }
        //g<<pozitie;break;
    }
    return 0;
}