Submission #909948

#	Time	Username	Problem	Language	Result	Execution time	Memory
909948		danikoynov	Progression (NOI20_progression)	C++14	100 / 100	1793 ms	163144 KiB

Progression

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const ll maxn = 3e5 + 10;

ll n, q;
ll d[maxn], b[maxn];

void input()
{
    cin >> n >> q;
    for (ll i = 1; i <= n; i ++)
    {
        cin >> d[i];
        b[i] = d[i] - d[i - 1];
    }
}

ll query(ll l, ll r)
{
    if (l == r)
        return 1;

    ll cnt = 1, mx = 0;
    for (ll i = l + 2; i <= r; i ++)
    {
        if (b[i] == b[i -1])
            cnt ++;
        else
        {
            if (cnt > mx)
                mx = cnt;
            cnt = 1;
        }
    }
    if (cnt > mx)
        mx = cnt;
    return mx + 1;
}

const ll inf = 2e18;

struct line
{
    ll k, m;

    line(ll _k = 0, ll _m = 0)
    {
        k = _k;
        m = _m;
    }

    ll math(ll x)
    {
        return k * x + m;
    }

    void add_line(line cur)
    {
        k += cur.k;
        m += cur.m;
    }

    void set_line(line cur)
    {
        k = cur.k;
        m = cur.m;
    }
};

line set_lazy[4 * maxn], add_lazy[4 * maxn];
ll set_tag[4 * maxn], add_tag[4 * maxn];

void push_lazy(ll root, ll left, ll right)
{
    ll mid = (left + right) / 2;
    if (set_tag[root] == 1)
    {
        ///li_chao[root].set_line(set_lazy[root]);
        if (left != right)
        {
            set_tag[root * 2] = 1;
            set_tag[root * 2 + 1] = 1;
            add_tag[root * 2] = 0;
            add_tag[root * 2 + 1] = 0;
            set_lazy[root * 2] = set_lazy[root];
            set_lazy[root * 2 + 1] = set_lazy[root];
            add_lazy[root * 2] = line(0, 0);
            add_lazy[root * 2 + 1] = line(0, 0);
        }
        else
        {
            d[left] = set_lazy[root].math(left);
        }
        set_tag[root] = 0;
        set_lazy[root] = line(0, 0);
    }
    if (add_tag[root] == 1)
    {

        if (left != right)
        {
            add_tag[root * 2] = 1;
            add_tag[root * 2 + 1] = 1;
            add_lazy[root * 2].add_line(add_lazy[root]);
            add_lazy[root * 2 + 1].add_line(add_lazy[root]);
        }
        else
        {
            d[left] += add_lazy[root].math(left);
        }
        add_tag[root] = 0;
        add_lazy[root] = line(0, 0);
    }
}

void set_line(ll root, ll left, ll right, ll qleft, ll qright, line cur)
{
    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        set_tag[root] = 1;
        set_lazy[root] = cur;
        push_lazy(root, left, right);
        return;
    }

    ll mid = (left + right) / 2;
    set_line(root * 2, left, mid, qleft, qright, cur);
    set_line(root * 2 + 1, mid + 1, right, qleft, qright, cur);
}

void add_line(ll root, ll left, ll right, ll qleft, ll qright, line cur)
{
    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        add_tag[root] = 1;
        add_lazy[root] = cur;
        push_lazy(root, left, right);
        return;
    }

    ll mid = (left + right) / 2;
    add_line(root * 2, left, mid, qleft, qright, cur);
    add_line(root * 2 + 1, mid + 1, right, qleft, qright, cur);
}


ll query(ll root, ll left, ll right, ll pos)
{
    push_lazy(root, left, right);
    if (left == right)
        return d[left];

    ll mid = (left + right) / 2;
    if (pos <= mid)
        return query(root * 2, left, mid, pos);
    return query(root * 2 + 1, mid + 1, right, pos);
}
/**void add_line_concious(ll root, ll left, ll right, line cur)
{
    push_lazy(root, left, right);
    ll mid = (left + right) / 2;
    if (li_chao[root].math(mid) < cur.math(mid))
        swap(li_chao[root], cur);

    if (left == right)
        return;

    if ()
}*/

struct node
{
    ll pref, suff, lon, len;
    ll fs, ls;

    node(ll _pref = 0, ll _suff = 0, ll _lon = 0, ll _fs = -inf, ll _ls = inf, ll _len = 0)
    {
        len = _len;
        pref = _pref;
        suff = _suff;
        lon = _lon;
        fs = _fs;
        ls = _ls;
    }
};

node merge_nodes(node lf, node rf)
{
    if (lf.ls == inf)
    return rf;
    if (rf.fs == -inf)
        return lf;

    node mf;
    mf.fs = lf.fs;
    mf.ls = rf.ls;

    mf.pref = lf.pref;
    if (lf.pref == lf.len && lf.ls == rf.fs)
        mf.pref += rf.pref;
    mf.suff = rf.suff;
    if (rf.suff == rf.len && rf.fs == lf.ls)
        mf.suff += lf.suff;

    mf.lon = max(lf.lon, rf.lon);
    if (lf.ls == rf.fs)
        mf.lon = max(mf.lon, lf.suff + rf.pref);

    mf.len = lf.len + rf.len;
    return mf;
}

node tree[4 * maxn];

pair < ll, ll > lazy[4 * maxn];
pair < ll, ll > tag[4 * maxn];
void make_lazy(ll root, ll left, ll right)
{
    if (tag[root].first)
    {
        ll len = right - left + 1;
        tree[root] = node(len, len, len, lazy[root].first, lazy[root].first, len);
        if (left != right)
        {
            tag[root * 2].first = 1;
            tag[root * 2 + 1].first = 1;
            tag[root * 2].second = 0;
            tag[root * 2 + 1].second = 0;
            lazy[root * 2].second = 0;
            lazy[root * 2 + 1].second = 0;

            lazy[root * 2].first = lazy[root].first;
            lazy[root * 2 + 1].first = lazy[root].first;
        }
        lazy[root].first = 0;
        tag[root].first = 0;
    }
    if (tag[root].second)
    {
        tree[root].fs += lazy[root].second;
        tree[root].ls += lazy[root].second;
        if (left != right)
        {
            tag[root * 2].second = 1;
            tag[root * 2 + 1].second = 1;
            lazy[root * 2].second += lazy[root].second;
            lazy[root * 2 + 1].second += lazy[root].second;
        }
        tag[root].second = 0;
        lazy[root].second = 0;
    }
}

void range_update_set(ll root, ll left, ll right, ll qleft, ll qright, ll val)
{
    make_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        lazy[root].first = val;
        tag[root].first = 1;
        make_lazy(root, left, right);
        return;
    }

    ll mid = (left + right) / 2;
    range_update_set(root * 2, left, mid, qleft, qright, val);
    range_update_set(root * 2 + 1, mid + 1, right, qleft, qright, val);

    tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
}

void range_update_add(ll root, ll left, ll right, ll qleft, ll qright, ll val)
{
    make_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        lazy[root].second =val;
        tag[root].second = 1;
        make_lazy(root, left, right);
        return;
    }

    ll mid = (left + right) / 2;
    range_update_add(root * 2, left, mid, qleft, qright, val);
    range_update_add(root * 2 + 1, mid + 1, right, qleft, qright, val);

    tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
}

node query_range(ll root, ll left, ll right, ll qleft, ll qright)
{
    make_lazy(root, left, right);
    if (left > qright || right < qleft)
        return node();

    if (left >= qleft && right <= qright)
    {
        return tree[root];
    }

    ll mid = (left + right) / 2;
    return merge_nodes(query_range(root * 2, left, mid, qleft, qright),
                       query_range(root * 2 + 1, mid + 1, right, qleft, qright));
}

void build_tree(ll root, ll left, ll right)
{
    if (left == right)
    {
        tree[root] = node(1, 1, 1, b[left], b[left], 1);
        return;
    }

    ll mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);

    tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
}

void simulate()
{
    build_tree(1, 1, n);
    for (ll i = 1; i <= q; i ++)
    {
        ll type, l, r;
        ll s, c;
        cin >> type >> l >> r;
        if (type == 3)
        {
            node cur = query_range(1, 1, n, l + 1, r);
            cout << cur.lon + 1 << endl;
            ///cout << query(l, r) << endl;
        }
        else if (type == 1)
        {
            cin >> s >> c;
            add_line(1, 1, n, l, r, line(c, - l * c + s));
            /*for (ll j = l; j <= r; j ++)
            {
                d[j] += s + (ll)(j - l) * c;
            }*/
            range_update_add(1, 1, n, l + 1, r, c);
            range_update_add(1, 1, n, l, l, s);
            //b[l] += s;
            //for (ll j = l + 1; j <= r; j ++)
              //  b[j] += c;
                if (r + 1 <= n)
            range_update_set(1, 1, n, r + 1, r + 1, query(1, 1, n, r + 1) - query(1, 1, n, r));
           // b[r + 1] = query(1, 1, n, r + 1) - query(1, 1, n, r); ///d[r + 1] - d[r];
        }
        else
        {
            cin >> s >> c;
            set_line(1, 1, n, l, r, line(c, - l * c + s));
            /**for (ll j = l; j <= r; j ++)
            {
                d[j] = s + (ll)(j - l) * c;
            }*/
            range_update_set(1, 1, n, l + 1, r, c);
            //for (ll j = l + 1; j <= r; j ++)
              //  b[j] = c;
            range_update_set(1, 1, n, l, l, query(1, 1, n, l) - query(1, 1, n, l - 1));
            ///b[l] = query(1, 1, n, l) - query(1, 1, n, l - 1); ///d[l] - d[l - 1];
            if (r + 1 <= n)
            range_update_set(1, 1, n, r + 1, r + 1, query(1, 1, n, r + 1) - query(1, 1, n, r));
            //b[r + 1] = query(1, 1, n, r + 1) - query(1, 1, n, r); ///d[r + 1] - d[r];
        }

        /**for (ll j = 2; j <= n; j ++)
        {
            if (b[j] != query_range(1, 1, n, j, j).fs)
            {
                while(true);
            }
        }*/
        /**for (ll j = 1; j <= n; j ++)
        {

            b[j] = d[j] - d[j - 1];
        }*/
        /**for (ll j = 1; j <= n; j ++)
            cout << d[j] << " ";
        cout << endl;*/
    }
}
void solve()
{
    input();
    simulate();
}

int main()
{
    speed();
    solve();
    return 0;
}

Compilation message (stderr)

Progression.cpp: In function 'void push_lazy(ll, ll, ll)':
Progression.cpp:93:8: warning: unused variable 'mid' [-Wunused-variable]
   93 |     ll mid = (left + right) / 2;
      |        ^~~

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