Submission #90551

#TimeUsernameProblemLanguageResultExecution timeMemory
90551Bodo171Weighting stones (IZhO11_stones)C++14
100 / 100
39 ms15640 KiB
#include <iostream>
#include <fstream>
using namespace std;
const int nmax=100005;
struct node
{
    int sum,minsuf,maxsuf;
}arb[4*nmax];
string ans;
int n,poz,wh,i,val;
void update(int nod,int l,int r)
{
    if(l==r)
    {
        arb[nod].sum=arb[nod].maxsuf=arb[nod].minsuf=val;
        return;
    }
    int m=(l+r)/2;
    if(poz<=m) update(2*nod,l,m);
    else update(2*nod+1,m+1,r);
    arb[nod].maxsuf=max(arb[2*nod+1].maxsuf,arb[2*nod+1].sum+arb[2*nod].maxsuf);
    arb[nod].minsuf=min(arb[2*nod+1].minsuf,arb[2*nod+1].sum+arb[2*nod].minsuf);
    arb[nod].sum=arb[2*nod].sum+arb[2*nod+1].sum;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>poz>>wh;
        if(wh==1) val=1;
        else val=-1;
        update(1,1,n);
        if(arb[1].minsuf>=0&&arb[1].maxsuf>0) ans+=">\n";
        else
        {
            if(arb[1].maxsuf<=0) ans+="<\n";
            else ans+="?\n";
        }
    }
    cout<<ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...