Cod sursa(job #2461819)

Utilizator stefantagaTaga Stefan stefantaga Data 26 septembrie 2019 10:42:16
Problema Walls Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.29 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);
    }
    if (poz>mij)
    {
        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 ua,int ub)
{
    if (ua<=st&&dr<=ub)
    {
        return arb[nod];
    }
    int r1=0,r2=0,mij=(st+dr)/2;
    if (ua<=mij)
    {
        r1=query(st,mij,2*nod,ua,ub);
    }
    if (mij<ub)
    {
        r2=query(mij+1,dr,2*nod+1,ua,ub);
    }
    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;
            }
        }
        if (query(1,n,1,1,sol)<niv)
        {
            g<<"MISS"<<'\n';
        }
        else
        {
            st=1;
            dr=sol;
            while (st<=dr)
            {
                mij=(st+dr)/2;
                if (query(1,n,1,mij,dr)>=niv)
                {
                    st=mij+1;
                }
                else
                {
                    dr=mij-1;
                }
            }
            pozitie=dr;
            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;
}