Submission #1227310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227310		jer033	Progression (NOI20_progression)	C++20	48 / 100	874 ms	53492 KiB

Progression

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

struct segTree
{
    ll l, r;
    ll diff;
    segTree* lef_child; segTree* rig_child;
    ll zero_streak;
    ll zero_streak_end;
    ll zero_streak_front;

    void update_zero_streak_front()
    {
        if (lef_child!=nullptr)
        {
            if ((lef_child->zero_streak_front) == ((lef_child->r) - (lef_child->l) + 1))
                zero_streak_front = lef_child->zero_streak_front + rig_child->zero_streak_front;
            else
                zero_streak_front = lef_child->zero_streak_front;
        }
        else
        {
            if (diff == 0ll)
                zero_streak_front = 1;
            else
                zero_streak_front = 0;
        }
    }

    void update_zero_streak_end()
    {
        if (rig_child!=nullptr)
        {
            if ((rig_child->zero_streak_end) == ((rig_child->r) - (rig_child->l) + 1))
                zero_streak_end = lef_child->zero_streak_end + rig_child->zero_streak_end;
            else
                zero_streak_end = rig_child->zero_streak_end;
        }
        else
        {
            if (diff == 0ll)
                zero_streak_end = 1;
            else
                zero_streak_end = 0;
        }
    }

    void update_zero_streak()
    {
        if (rig_child!=nullptr)
        {
            zero_streak = max(max(lef_child->zero_streak, rig_child->zero_streak), lef_child->zero_streak_end+rig_child->zero_streak_front);
        }
        else
        {
            if (diff == 0ll)
                zero_streak = 1;
            else
                zero_streak = 0;
        }
    }

    segTree(int li, int ri, vector<ll> (&ddiff))
    {
        l = li; r = ri;
        if (l==r)
        {
            diff = ddiff[l];
        }
        else
        {
            int mid = (li+ri)/2;
            lef_child = new segTree(li, mid, ddiff);
            rig_child = new segTree(mid+1, ri, ddiff);
        }
        update_zero_streak_end();
        update_zero_streak_front();
        update_zero_streak();
    }

    void update(ll ind, ll add)
    {
        if ((l<=ind) and (ind<=r))
        {
            if (lef_child!=nullptr)
            {
                lef_child->update(ind, add);
                rig_child->update(ind, add);
            }
            else
                diff += add;
            update_zero_streak_end();
            update_zero_streak_front();
            update_zero_streak();
        }
    }

    ll answer_query(ll lef, ll rig)
    {
        ll overlap_lef = max(lef, l);
        ll overlap_rig = min(rig, r);
        if (overlap_lef > overlap_rig)
            return 0;
        if ((overlap_lef==l) and (overlap_rig==r))
            return zero_streak;
        //children should exist
        ll cand_1 = max(lef_child->answer_query(lef, rig), rig_child->answer_query(lef, rig));
        ll cand_2 = 0;
        if ((lef_child->r <= rig) and (rig_child->l >= lef))
            cand_2 = min((lef_child->r)-lef+1, lef_child->zero_streak_end) + min(rig-(rig_child->l)+1, rig_child->zero_streak_front);
        return max(cand_1, cand_2);
    }
};

int main()
{
    int N, Q; cin >> N >> Q;
    vector<ll> diff(N);
    for (int i=0; i<N; i++)
        cin >> diff[i];
    vector<ll> ddiff(N);
    for (int i=1; i<(N-1); i++)
        ddiff[i] = 2ll*diff[i]-diff[i-1]-diff[i+1];
    segTree ree(0, N-1, ddiff);
    //cout << "done\n";
    while (Q--)
    {
        int typ; cin >> typ;
        if (typ == 1)
        {
            ll l, r, s, c;
            cin >> l >> r >> s >> c;
            l--; r--;
            ree.update(l-1, 0ll-s);
            ree.update(l, s-c);
            ree.update(r, s+(r-l+1)*c);
            ree.update(r+1, 0-(s+(r-l)*c));
        }
        else
        {
            ll l, r;
            cin >> l >> r;
            l--; r--;
            if ((r-l)<=1ll)
                cout << r-l+1ll << '\n';
            else
            {
                ll ans = ree.answer_query(l+1, r-1);
                cout << ans+2ll << '\n';
            }
        }
    }
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 15
• Subtask 3: 35 / 35
• Subtask 4: 0 / 11
• Subtask 5: 13 / 13
• Subtask 6: 0 / 17