Submission #524732

#	Time	Username	Problem	Language	Result	Execution time	Memory
524732		TheKingAleks	Weighting stones (IZhO11_stones)	C++14	100 / 100	153 ms	4420 KiB

stones

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6+2;
pair<int,int> tree[MAX_N*4];
int lazy[MAX_N*4];
void update(int node, int tl, int tr, int l, int r, int val)
{
    if(lazy[node])
    {
        tree[node].first += lazy[node];
        tree[node].second += lazy[node];
        if(tl != tr)
        {
            lazy[node*2]+=lazy[node];
            lazy[node*2+1]+=lazy[node];
        }
        lazy[node] = 0;
    }
    if(tl >= l && tr <= r)
    {
        tree[node].first += val;
        tree[node].second += val;
        if(tl != tr)
        {
            lazy[node*2]+=val;
            lazy[node*2+1]+=val;
        }
        return;
    }
    if(tl > r || tr < l) return;
    int mid = (tl+tr)/2;
    update(node*2, tl, mid, l, r, val);
    update(node*2+1, mid+1, tr, l, r, val);
    tree[node].first = max(tree[node*2].first,tree[node*2+1].first);
    tree[node].second = min(tree[node*2].second,tree[node*2+1].second);
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int s;
    cin>>s;
    for(int i=0; i<s; i++)
    {
        int val,flag;
        cin>>val>>flag;
        if(flag == 1)
        {
            update(1,1,100002,1,val,1);
        }
        else
        {
            update(1,1,100002,1,val,-1);
        }
        if(tree[1].first >= 0 && tree[1].second >= 0) cout<<">"<<endl;
        else if(tree[1].first <= 0 && tree[1].second <= 0) cout<<"<"<<endl;
        else cout<<"?"<<endl;

    }
}

• Subtask 1: 100 / 100