Submission #1093349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093349		vyshniak_n	Progression (NOI20_progression)	C++17	44 / 100	544 ms	91624 KiB

Progression

//#pragma optimize("Ofast")
//#pragma optimize("unroll-loops")
//#pragma traget("avx,avx2,tune=native")
 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
#define el '\n'
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define point pair <ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
using namespace std;
 
#include <random>
mt19937 rnd(time(0));
 
const ll INF = 2e18 + 10;
const ll inf = 2e9 + 10;
const ll N = 3e5 + 10;
const ll mod = 998244353;
const ll LOG = 20;

struct node {
    ll mx;
    ll sum;
    ll l;
    ll vall;
    ll r;
    ll valr;
    ll sum_d;

    node() = default;

    node(ll x, ll len) {
        mx = sum = l = r = len;
        vall = x;
        valr = x;
        sum_d = len * x;
    }

    node(node ql, node qr) {
        if (ql.sum != 0 && qr.sum != 0)
            sum = ql.sum + qr.sum;

        mx = max(ql.mx, qr.mx);
        if (ql.valr == qr.vall)
            mx = max(mx, ql.r + qr.l);

        if (mx != sum) sum = 0;

        vall = ql.vall;
        valr = qr.valr;

        l = ql.l;
        if (ql.sum != 0 && ql.vall == qr.vall)
            l = max(l, ql.sum + qr.l);

        r = qr.r;
        if (qr.sum != 0 && qr.valr == ql.valr)
            r = max(l, qr.sum + ql.r);
        sum_d = ql.sum_d + qr.sum_d;
    }

    void add(ll x, ll len) {
        vall += x;
        valr += x;
        sum_d += len * x;
    }
};

node t[4 * N];
ll lazy_add[4 * N];
ll lazy_rm[4 * N];
ll len[4 * N];
ll d[N];

void build(ll v, ll tl, ll tr) {
    if (tl == tr) {
        len[v] = 1;
        t[v] = node(d[tl] - d[tl - 1], 1);
        return;
    }

    ll tm = (tl + tr) >> 1;

    build(v << 1, tl, tm);
    build(v << 1 | 1, tm + 1, tr);

    t[v] = node(t[v << 1], t[v << 1 | 1]);
    len[v] = len[v << 1] + len[v << 1 | 1];
}

void push(ll v) {
    if (lazy_rm[v] != -INF) {
        lazy_add[v << 1] = lazy_add[v << 1 | 1] = 0;

        t[v << 1] = node(lazy_rm[v], len[v << 1]);
        t[v << 1 | 1] = node(lazy_rm[v], len[v << 1 | 1]);

        lazy_rm[v << 1] = lazy_rm[v << 1 | 1] = lazy_rm[v];
        lazy_rm[v] = -INF;
    }

    t[v << 1].add(lazy_add[v], len[v << 1]);
    t[v << 1 | 1].add(lazy_add[v], len[v << 1 | 1]);

    lazy_add[v << 1] += lazy_add[v];
    lazy_add[v << 1 | 1] += lazy_add[v];
    lazy_add[v] = 0;
}
void upd_add(ll v, ll tl, ll tr, ll l, ll r, ll x) {
    if (l > tr || r < tl)
        return;
    if (l <= tl && r >= tr) {
        t[v].add(x, len[v]);
        lazy_add[v] += x;
        return;
    }

    push(v);
    ll tm = (tl + tr) >> 1;

    upd_add(v << 1, tl, tm, l, r, x);
    upd_add(v << 1 | 1, tm + 1, tr, l, r, x);

    t[v] = node(t[v << 1], t[v << 1 | 1]);
}
void upd(ll v, ll tl, ll tr, ll l, ll r, ll x) {
    if (l > tr || r < tl)
        return;
    if (l <= tl && r >= tr) {
        lazy_add[v] = 0;
        lazy_rm[v] = x;
        t[v] = node(x, len[v]);
        return;
    }

    push(v);
    ll tm = (tl + tr) >> 1;

    upd(v << 1, tl, tm, l, r, x);
    upd(v << 1 | 1, tm + 1, tr, l, r, x);

    t[v] = node(t[v << 1], t[v << 1 | 1]);
}
node get(ll v, ll tl, ll tr, ll l, ll r) {
    if (l > tr || r < tl)
        return node(-inf, 0);
    if (l <= tl && r >= tr)
        return t[v];

    push(v);
    ll tm = (tl + tr) >> 1;

    return node(get(v << 1, tl, tm, l, r),
                get(v << 1 | 1, tm + 1, tr, l, r));
}
ll get_pos(ll v, ll tl, ll tr, ll l, ll r) {
    if (l > r || l > tr || r < tl)
        return 0;
    if (l <= tl && r >= tr)
        return t[v].sum_d;

    push(v);
    ll tm = (tl + tr) >> 1;

    return get_pos(v << 1, tl, tm, l, r) +
           get_pos(v << 1 | 1, tm + 1, tr, l, r);
}

void solve() {
    ll n, q;
    cin >> n >> q;

    d[0] = INF;
    for (ll i = 1; i <= n; i++)
        cin >> d[i];
    for (ll i = 0; i < 4 * N; i++)
        lazy_rm[i] = -INF;

    build(1, 1, n);
    ll f = d[1];

    while (q--) {
        ll t, l, r, s, c;
        cin >> t;

        if (t == 1) {
            cin >> l >> r >> s >> c;
            if (l != r)
                upd_add(1, 1, n, l + 1, r, c);
            if (l != 1)
                upd_add(1, 1, n, l, l, s);
            if (r != n)
                upd_add(1, 1, n, r + 1, r + 1, -(s + (r - l) * c));
            if (l == 1)
                f += s;
        } else if (t == 2) {
            cin >> l >> r >> s >> c;
            ll vall, valr;
            if (l != 1) vall = f + get_pos(1, 1, n, 2, l - 1);
            if (r != n) valr = f + get_pos(1, 1, n, 2, r + 1);
            if (l != r)
                upd(1, 1, n, l + 1, r, c);
            if (l != 1)
                upd(1, 1, n, l, l, s - vall);
            if (r != n)
                upd(1, 1, n, l, l, valr - (s + (r - l) * c));
            if (l == 1)
                f = s;
        } else {
            cin >> l >> r;
            if (l == r) {
                cout << 1 << el;
                continue;
            }

            cout << get(1, 1, n, l + 1, r).mx + 1 << el;
        }
    }
    return;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);

    int tests = 1;
    //cin >> tests;
 
    while (tests--) 
        solve();
    return 0;
}
/*
*/

Compilation message (stderr)

Progression.cpp: In function 'void solve()':
Progression.cpp:247:20: warning: 'valr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  247 |                 upd(1, 1, n, l, l, valr - (s + (r - l) * c));
      |                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:245:20: warning: 'vall' may be used uninitialized in this function [-Wmaybe-uninitialized]
  245 |                 upd(1, 1, n, l, l, s - vall);
      |                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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