Submission #984038

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
984038	2024-05-16T09:29:31 Z	sofija6	Weighting stones (IZhO11_stones)	C++14	100 / 100	54 ms	7696 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	456 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	4 ms	1112 KB	Output is correct
11	Correct	25 ms	4068 KB	Output is correct
12	Correct	42 ms	7356 KB	Output is correct
13	Correct	43 ms	7508 KB	Output is correct
14	Correct	43 ms	7504 KB	Output is correct
15	Correct	42 ms	7504 KB	Output is correct
16	Correct	43 ms	7508 KB	Output is correct
17	Correct	54 ms	7504 KB	Output is correct
18	Correct	43 ms	7512 KB	Output is correct
19	Correct	42 ms	7328 KB	Output is correct
20	Correct	42 ms	7436 KB	Output is correct
21	Correct	50 ms	7364 KB	Output is correct
22	Correct	43 ms	7696 KB	Output is correct
23	Correct	42 ms	7508 KB	Output is correct
24	Correct	42 ms	7344 KB	Output is correct
25	Correct	42 ms	7504 KB	Output is correct