oj.uz

Submission #1093370

# Submission time Handle Problem Language Result Execution time Memory
1093370 2024-09-26T17:52:41 Z vyshniak_n Progression (NOI20_progression) C++17
44 / 100
 535 ms 95312 KB 
//#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

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

# Verdict Execution time Memory Grader output
1 Correct 204 ms 78420 KB Output is correct
2 Correct 80 ms 10064 KB Output is correct
3 Correct 82 ms 10064 KB Output is correct
4 Correct 75 ms 10064 KB Output is correct
5 Correct 77 ms 10244 KB Output is correct
6 Correct 81 ms 10060 KB Output is correct
7 Correct 76 ms 10064 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 209 ms 78420 KB Output is correct
12 Correct 213 ms 78296 KB Output is correct
13 Correct 216 ms 78672 KB Output is correct
14 Correct 241 ms 78676 KB Output is correct
15 Correct 212 ms 78748 KB Output is correct
16 Correct 207 ms 78416 KB Output is correct
17 Correct 209 ms 86356 KB Output is correct
18 Correct 225 ms 86356 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 86940 KB Output is correct
2 Correct 68 ms 10324 KB Output is correct
3 Correct 70 ms 10320 KB Output is correct
4 Correct 54 ms 10460 KB Output is correct
5 Correct 66 ms 10372 KB Output is correct
6 Correct 68 ms 10392 KB Output is correct
7 Correct 69 ms 10324 KB Output is correct
8 Correct 5 ms 9816 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 290 ms 86648 KB Output is correct
12 Correct 274 ms 93012 KB Output is correct
13 Correct 289 ms 91732 KB Output is correct
14 Correct 300 ms 91696 KB Output is correct
15 Correct 263 ms 93108 KB Output is correct
16 Correct 299 ms 93520 KB Output is correct
17 Correct 311 ms 93520 KB Output is correct
18 Correct 290 ms 93584 KB Output is correct
19 Correct 280 ms 93012 KB Output is correct
20 Correct 263 ms 92896 KB Output is correct
21 Correct 309 ms 92956 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 488 ms 86352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 86940 KB Output is correct
2 Correct 68 ms 10324 KB Output is correct
3 Correct 70 ms 10320 KB Output is correct
4 Correct 54 ms 10460 KB Output is correct
5 Correct 66 ms 10372 KB Output is correct
6 Correct 68 ms 10392 KB Output is correct
7 Correct 69 ms 10324 KB Output is correct
8 Correct 5 ms 9816 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 290 ms 86648 KB Output is correct
12 Correct 274 ms 93012 KB Output is correct
13 Correct 289 ms 91732 KB Output is correct
14 Correct 300 ms 91696 KB Output is correct
15 Correct 263 ms 93108 KB Output is correct
16 Correct 299 ms 93520 KB Output is correct
17 Correct 311 ms 93520 KB Output is correct
18 Correct 290 ms 93584 KB Output is correct
19 Correct 280 ms 93012 KB Output is correct
20 Correct 263 ms 92896 KB Output is correct
21 Correct 309 ms 92956 KB Output is correct
22 Correct 528 ms 95312 KB Output is correct
23 Correct 95 ms 13132 KB Output is correct
24 Correct 91 ms 12880 KB Output is correct
25 Correct 98 ms 13004 KB Output is correct
26 Correct 97 ms 13020 KB Output is correct
27 Correct 95 ms 13040 KB Output is correct
28 Correct 96 ms 13000 KB Output is correct
29 Correct 4 ms 9820 KB Output is correct
30 Correct 4 ms 9820 KB Output is correct
31 Correct 4 ms 9820 KB Output is correct
32 Incorrect 535 ms 92580 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 78420 KB Output is correct
2 Correct 80 ms 10064 KB Output is correct
3 Correct 82 ms 10064 KB Output is correct
4 Correct 75 ms 10064 KB Output is correct
5 Correct 77 ms 10244 KB Output is correct
6 Correct 81 ms 10060 KB Output is correct
7 Correct 76 ms 10064 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 209 ms 78420 KB Output is correct
12 Correct 213 ms 78296 KB Output is correct
13 Correct 216 ms 78672 KB Output is correct
14 Correct 241 ms 78676 KB Output is correct
15 Correct 212 ms 78748 KB Output is correct
16 Correct 207 ms 78416 KB Output is correct
17 Correct 209 ms 86356 KB Output is correct
18 Correct 225 ms 86356 KB Output is correct
19 Incorrect 5 ms 9816 KB Output isn't correct
20 Halted 0 ms 0 KB -