Cod sursa(job #2461840)

Utilizator stefantagaTaga Stefan stefantaga Data 26 septembrie 2019 11:13:51
Problema Walls Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 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,coord[100005];
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 posx, int posy )
{
    if( posx<coord[st]||posy>arb[nod]||st>dr)
        return -1;
    if( st == dr )
        return st;

    int mij=(st+dr)/2,res;
    res = query( mij+1,dr,2*nod+1,posx,posy);
    if(res==-1)
        res=query( st,mij,2*nod,posx,posy);
    return res;
}
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);
    }
coord[1]=1;
for (i=2;i<=n;i++)
{
      coord[i]=coord[i-1]+v[i-1].gr+1;
}
    f>>m;
    for (i=1;i<=m;i++)
    {
        f>>poz>>niv;
        pozitie=query(1,n,1,poz,niv);
        if (pozitie==-1)
        {
            g<<"MISS"<<'\n';
        }
        else
        {
            g<<"HIT"<<" ";
            g<<coord[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;
}