Submission #881952

#	Time	Username	Problem	Language	Result	Execution time	Memory
881952		noyancanturk	Weighting stones (IZhO11_stones)	C++17	100 / 100	42 ms	10372 KiB

stones

#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=1e5+100;
#else
    const int lim=3e3;
#endif

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back

const int mod=1e9+7;
using pii=pair<int,int>;

struct segtree{
    int n,lazy[4*lim];
    pii tree[4*lim];
    segtree(int n):n(n){
        memset(lazy,0,sizeof(lazy));
        fill(tree,tree+4*lim,pii{0,0});
    }
    void push(int node,int l,int r){
        if(!lazy[node])return;
        tree[node].first+=lazy[node];
        tree[node].second+=lazy[node];
        if(l^r){
            int child=node<<1;
            lazy[child]+=lazy[node];
            lazy[child|1]+=lazy[node];
        }
        lazy[node]=0;
    }
    int L,R,VAL;
    pii merge(pii v1,pii v2){
        return pii{min(v1.first,v2.first),max(v1.second,v2.second)};
    }
    pii update(int l,int r,int node){
        push(node,l,r);
        if(r<L||R<l){
            return tree[node];
        }
        if(L<=l&&r<=R){
            lazy[node]+=VAL;
            push(node,l,r);
            return tree[node];
        }
        int mid=(l+r)>>1,child=node<<1;
        return tree[node]=merge(update(l,mid,child),update(mid+1,r,child|1));
    }
    void Update(int l,int r,int val){
        L=l,R=r,VAL=val;
        update(1,n,1);
    }
};

void solve(){
    int n;
    cin>>n;
    segtree a(n);
    for(int i=0;i<n;i++){
        int v,s;
        cin>>v>>s;
        a.Update(1,v,s==1?1:-1);
        if(a.tree[1].first<0&&0<a.tree[1].second){
            cout<<"?\n";
        }else if(a.tree[1].first<0){
            cout<<"<\n";
        }else{
            cout<<">\n";
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

• Subtask 1: 100 / 100