Submission #1046902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046902		12345678	Weighting stones (IZhO11_stones)	C++17	100 / 100	42 ms	4680 KiB

stones

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;

int n, x, t;

struct segtree
{
    int mn[4*nx], mx[4*nx], lz[4*nx];
    void pushlz(int l, int r, int i)
    {
        mn[i]+=lz[i];
        mx[i]+=lz[i];
        if (l!=r) lz[2*i]+=lz[i], lz[2*i+1]+=lz[i];
        lz[i]=0;
    }
    void update(int l, int r, int i, int ql, int qr, int vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return lz[i]+=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr, vl);
        update(md+1, r, 2*i+1, ql, qr, vl);
        mn[i]=min(mn[2*i], mn[2*i+1]);
        mx[i]=max(mx[2*i], mx[2*i+1]);
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++)
    {
        cin>>x>>t;
        x=n-x+1;
        if (t==1) s.update(1, n, 1, x, n, 1);
        else s.update(1, n, 1, x, n, -1);
        if (s.mn[1]>=0) cout<<">\n";
        else if (s.mx[1]<=0) cout<<"<\n";
        else cout<<"?\n";
    }
}

• Subtask 1: 100 / 100