Submission #984038

#	Time	Username	Problem	Language	Result	Execution time	Memory
984038		sofija6	Weighting stones (IZhO11_stones)	C++14	100 / 100	54 ms	7696 KiB

stones

#include <bits/stdc++.h>
#define ll long long
#define llinf 10000000000000000
using namespace std;
struct element
{
    ll minn,maxx;
};
element Merge(element x,element y)
{
    return {min(x.minn,y.minn),max(x.maxx,y.maxx)};
}
ll n,sz;
element neutral={llinf,-llinf};
struct seg_tree
{
    vector<element> st;
    vector<ll> lazy;
    void Init()
    {
        sz=1;
        while (sz<n)
            sz <<= 1;
        st.resize(2*sz+2,neutral);
        lazy.resize(2*sz+2);
    }
    void Build()
    {
        for (ll i=sz;i<sz+n;i++)
            st[i]={0,0};
        for (ll i=sz-1;i>=0;i--)
            st[i]=Merge(st[2*i],st[2*i+1]);
    }
    void Propagate(ll x)
    {
        st[x].minn+=lazy[x];
        st[x].maxx+=lazy[x];
        if (x<sz)
        {
            lazy[2*x]+=lazy[x];
            lazy[2*x+1]+=lazy[x];
        }
        lazy[x]=0;
    }
    void Update(ll l,ll r,ll val,ll x,ll lx,ll rx)
    {
        Propagate(x);
        if (lx>r || rx<l)
            return;
        if (lx>=l && rx<=r)
        {
            lazy[x]+=val;
            Propagate(x);
            return;
        }
        ll mid=(lx+rx)/2;
        Update(l,r,val,2*x,lx,mid);
        Update(l,r,val,2*x+1,mid+1,rx);
        st[x]=Merge(st[2*x],st[2*x+1]);
    }
    element Calc()
    {
        Propagate(1);
        return st[1];
    }
};
seg_tree S;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll r,s;
    cin >> n;
    S.Init();
    S.Build();
    for (ll i=1;i<=n;i++)
    {
        cin >> r >> s;
        if (s==1)
            S.Update(1,r,1,1,1,sz);
        else
            S.Update(1,r,-1,1,1,sz);
        element ans=S.Calc();
        if (ans.minn>=0)
            cout << ">\n";
        else if (ans.maxx<=0)
            cout << "<\n";
        else
            cout << "?\n";
    }
    return 0;
}

• Subtask 1: 100 / 100