oj.uz

Submission #1093349

# Submission time Handle Problem Language Result Execution time Memory
1093349 2024-09-26T16:59:40 Z vyshniak_n Progression (NOI20_progression) C++17
44 / 100
 544 ms 91624 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 223 ms 82784 KB Output is correct
2 Correct 86 ms 11976 KB Output is correct
3 Correct 78 ms 11872 KB Output is correct
4 Correct 79 ms 11824 KB Output is correct
5 Correct 79 ms 11872 KB Output is correct
6 Correct 88 ms 11980 KB Output is correct
7 Correct 78 ms 11980 KB Output is correct
8 Correct 4 ms 9832 KB Output is correct
9 Correct 4 ms 9712 KB Output is correct
10 Correct 4 ms 9832 KB Output is correct
11 Correct 216 ms 82812 KB Output is correct
12 Correct 218 ms 82784 KB Output is correct
13 Correct 235 ms 83040 KB Output is correct
14 Correct 215 ms 83036 KB Output is correct
15 Correct 219 ms 82772 KB Output is correct
16 Correct 211 ms 82836 KB Output is correct
17 Correct 212 ms 82804 KB Output is correct
18 Correct 225 ms 82772 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9820 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 272 ms 90204 KB Output is correct
2 Correct 69 ms 11600 KB Output is correct
3 Correct 66 ms 11696 KB Output is correct
4 Correct 56 ms 11540 KB Output is correct
5 Correct 70 ms 11600 KB Output is correct
6 Correct 67 ms 11604 KB Output is correct
7 Correct 70 ms 11604 KB Output is correct
8 Correct 4 ms 9816 KB Output is correct
9 Correct 4 ms 9832 KB Output is correct
10 Correct 4 ms 9832 KB Output is correct
11 Correct 303 ms 89588 KB Output is correct
12 Correct 269 ms 90296 KB Output is correct
13 Correct 318 ms 89692 KB Output is correct
14 Correct 303 ms 89688 KB Output is correct
15 Correct 263 ms 90196 KB Output is correct
16 Correct 299 ms 90548 KB Output is correct
17 Correct 305 ms 90672 KB Output is correct
18 Correct 300 ms 90708 KB Output is correct
19 Correct 277 ms 90116 KB Output is correct
20 Correct 275 ms 90104 KB Output is correct
21 Correct 272 ms 89936 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 90204 KB Output is correct
2 Correct 69 ms 11600 KB Output is correct
3 Correct 66 ms 11696 KB Output is correct
4 Correct 56 ms 11540 KB Output is correct
5 Correct 70 ms 11600 KB Output is correct
6 Correct 67 ms 11604 KB Output is correct
7 Correct 70 ms 11604 KB Output is correct
8 Correct 4 ms 9816 KB Output is correct
9 Correct 4 ms 9832 KB Output is correct
10 Correct 4 ms 9832 KB Output is correct
11 Correct 303 ms 89588 KB Output is correct
12 Correct 269 ms 90296 KB Output is correct
13 Correct 318 ms 89692 KB Output is correct
14 Correct 303 ms 89688 KB Output is correct
15 Correct 263 ms 90196 KB Output is correct
16 Correct 299 ms 90548 KB Output is correct
17 Correct 305 ms 90672 KB Output is correct
18 Correct 300 ms 90708 KB Output is correct
19 Correct 277 ms 90116 KB Output is correct
20 Correct 275 ms 90104 KB Output is correct
21 Correct 272 ms 89936 KB Output is correct
22 Correct 532 ms 91064 KB Output is correct
23 Correct 96 ms 11860 KB Output is correct
24 Correct 98 ms 11764 KB Output is correct
25 Correct 91 ms 11860 KB Output is correct
26 Correct 102 ms 11888 KB Output is correct
27 Correct 95 ms 11772 KB Output is correct
28 Correct 96 ms 11860 KB Output is correct
29 Correct 4 ms 9816 KB Output is correct
30 Correct 4 ms 9820 KB Output is correct
31 Correct 4 ms 9820 KB Output is correct
32 Incorrect 544 ms 89768 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 82784 KB Output is correct
2 Correct 86 ms 11976 KB Output is correct
3 Correct 78 ms 11872 KB Output is correct
4 Correct 79 ms 11824 KB Output is correct
5 Correct 79 ms 11872 KB Output is correct
6 Correct 88 ms 11980 KB Output is correct
7 Correct 78 ms 11980 KB Output is correct
8 Correct 4 ms 9832 KB Output is correct
9 Correct 4 ms 9712 KB Output is correct
10 Correct 4 ms 9832 KB Output is correct
11 Correct 216 ms 82812 KB Output is correct
12 Correct 218 ms 82784 KB Output is correct
13 Correct 235 ms 83040 KB Output is correct
14 Correct 215 ms 83036 KB Output is correct
15 Correct 219 ms 82772 KB Output is correct
16 Correct 211 ms 82836 KB Output is correct
17 Correct 212 ms 82804 KB Output is correct
18 Correct 225 ms 82772 KB Output is correct
19 Incorrect 5 ms 9820 KB Output isn't correct
20 Halted 0 ms 0 KB -