Submission #1157725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157725		vicvic	Progression (NOI20_progression)	C++20	100 / 100	992 ms	116892 KiB

Progression

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdint>
#include <cassert>
#define int long long
using namespace std;
ifstream f ("test.in");
ofstream g ("test.out");
const int NMAX=3e5;
int v[NMAX+5], n, q;
class SegTree
{
public:
    struct node
    {
        int l, r, sm, pref, suf, pref_len, suf_len, lazy, lazy2, hi, reset, len;
        node ()
        {
            this -> l=this -> r=this -> sm=this -> pref=this -> suf=this -> pref_len=this -> suf_len=this -> lazy=this -> lazy2=this -> hi=this -> reset=this -> len=0;
        }
    } t[NMAX*4+5];
    node merge (node b, node a)
    {
        node ret;
        ret.l=b.l;
        ret.len=b.len+a.len;
        ret.hi=max (b.hi, a.hi);
        if (b.suf==a.pref)
            ret.hi=max (ret.hi, b.suf_len+a.pref_len);
        ret.r=a.r;
        ret.sm=a.sm+b.sm;
        ret.pref=b.pref;
        ret.suf=a.suf;
        ret.pref_len=b.pref_len;
        ret.suf_len=a.suf_len;
        if (b.pref==a.pref && b.pref_len==b.len) ret.pref_len+=a.pref_len;
        if (a.suf==b.suf && a.suf_len==a.len) ret.suf_len+=b.suf_len;
        return ret;
    }
    void actbuild (int nod, int st, int dr)
    {
        if (st==dr)
        {
            t[nod].hi=t[nod].pref_len=t[nod].suf_len=1;
            t[nod].sm=t[nod].pref=t[nod].suf=v[st]-v[st-1];
            t[nod].l=st;
            t[nod].r=dr;
            t[nod].len=1;
        }
        else
        {
            int mij =(st+dr) >> 1;
            actbuild (nod*2, st, mij);
            actbuild (nod*2+1, mij+1, dr);
            t[nod]=merge (t[nod*2], t[nod*2+1]);
        }
    }
    void build (int st, int dr)
    {
        actbuild (1, st, dr);
    }
    void prop (int nod)
    {
        if (t[nod].reset)
        {
            t[nod].suf_len=t[nod].pref_len=t[nod].hi=t[nod].len;
            t[nod].pref=t[nod].suf=t[nod].lazy2;
            t[nod].reset=0;
            t[nod].sm=t[nod].lazy2*(t[nod].len);
            if (t[nod].l!=t[nod].r)
            {
                t[nod*2].lazy2=t[nod].lazy2;
                t[nod*2+1].lazy2=t[nod].lazy2;
                t[nod*2].reset=t[nod*2+1].reset=1;
                t[nod*2].lazy=t[nod*2+1].lazy=0;
            }
        }
        else
        {
            t[nod].pref+=t[nod].lazy;
            t[nod].suf+=t[nod].lazy;
            t[nod].sm+=t[nod].lazy*(t[nod].len);
            if (t[nod].l!=t[nod].r)
            {
                if (!t[nod*2].reset) t[nod*2].lazy+=t[nod].lazy;
                else t[nod*2].lazy=0, t[nod*2].lazy2+=t[nod].lazy;
                if (!t[nod*2+1].reset) t[nod*2+1].lazy+=t[nod].lazy;
                else t[nod*2+1].lazy=0, t[nod*2+1].lazy2+=t[nod].lazy;
            }
        }
        t[nod].lazy=t[nod].lazy2=0;
    }
    void actupdate_type1 (int nod, int st, int dr, int stq, int drq, int val)
    {
        prop (nod);
        if (stq<=st && dr<=drq)
        {
            if (t[nod].reset) t[nod].lazy2+=val;
            else t[nod].lazy+=val;
            prop (nod);
        }
        else
        {
            int mij = (st+dr) >> 1;
            if (drq<=mij)
                actupdate_type1 (nod*2, st, mij, stq, drq, val);
            else if (stq>mij)
                actupdate_type1 (nod*2+1, mij+1, dr, stq, drq, val);
            else actupdate_type1 (nod*2, st, mij, stq, drq, val), actupdate_type1 (nod*2+1, mij+1, dr, stq, drq, val);
            prop (nod*2);
            prop (nod*2+1);
            t[nod]=merge (t[nod*2], t[nod*2+1]);
        }
    }
    void update_type1 (int st, int dr, int val)
    {
        if (!(st >= 1 && dr <= n && st <= dr))
            return;
        actupdate_type1 (1, 1, n, st, dr, val);
    }
    void actupdate_type2 (int nod, int st, int dr, int stq, int drq, int val)
    {
        prop (nod);
        if (stq<=st && dr<=drq)
        {
            t[nod].lazy2=val;
            t[nod].reset=1;
            t[nod].lazy=0;
            prop (nod);
        }
        else
        {
            int mij = (st+dr) >> 1;
            if (drq<=mij)
                actupdate_type2 (nod*2, st, mij, stq, drq, val);
            else if (stq>mij)
                actupdate_type2 (nod*2+1, mij+1, dr, stq, drq, val);
            else actupdate_type2 (nod*2, st, mij, stq, drq, val), actupdate_type2 (nod*2+1, mij+1, dr, stq, drq, val);
            prop (nod*2);
            prop (nod*2+1);
            t[nod]=merge (t[nod*2], t[nod*2+1]);
        }
    }
    void update_type2 (int st, int dr, int val)
    {
        if (!(st >= 1 && dr <= n && st <= dr))
            return;
        actupdate_type2 (1, 1, n, st, dr, val);
    }
    node actquery (int nod, int st, int dr, int stq, int drq)
    {
        prop (nod);
        if (stq<=st && dr<=drq)
        {
            return t[nod];
        }
        else
        {
            prop (nod*2);
            prop (nod*2+1);
            int mij = (st+dr) >> 1;
            if (drq<=mij)
                return actquery (nod*2, st, mij, stq, drq);
            else if (stq>mij)
                return actquery (nod*2+1, mij+1, dr, stq, drq);
            else return merge (actquery (nod*2, st, mij, stq, drq), actquery (nod*2+1, mij+1, dr, stq, drq));
        }
    }
    node query (int st, int dr)
    {
        if (!(st>=1 && dr<=n && st<=dr))
            return node ();
        return actquery (1, 1, n, st, dr);
    }
};
SegTree aint;
int32_t main ()
{
    ios :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> n >> q;
    for (int i=1;i<=n;i++)
    {
        cin >> v[i];
    }
    v[0]=0;
    aint.build (1, n);
    while (q--)
    {
        int type, st, dr;
        cin >> type >> st >> dr;
        if (type==3)
        {
            if (st==dr)
            {
                cout << 1 << "\n";
            }
            else cout << aint.query (st+1, dr).hi+1 << "\n";
        }
        else if (type==1)
        {
            int s, c;
            cin >> s >> c;
            aint.update_type1 (st, st, s);
            if (st<dr) aint.update_type1 (st+1, dr, c);
            if (dr<n) aint.update_type1 (dr+1, dr+1, -(s+(dr-st)*c));
        }
        else
        {
            int s, c;
            cin >> s >> c;
            int s2=0;
            if (dr<n) s2=aint.query (1, dr+1).sm;
            if (st>1)
            {
                int x=aint.query (1, st-1).sm;
                aint.update_type2 (st, st, s-x);
            }
            else
            {
                aint.update_type2 (1, 1, s);
            }
            if (st<dr)
            {
                aint.update_type2 (st+1, dr, c);
            }
            if (dr<n)
            {
                aint.update_type2 (dr+1, dr+1, s2-(s+(dr-st)*c));
            }
        }
    }
    return 0;
}

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