oj.uz

Submission #1093365

# Submission time Handle Problem Language Result Execution time Memory
1093365 2024-09-26T17:36:44 Z vyshniak_n Progression (NOI20_progression) C++17
44 / 100
 535 ms 95864 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], tl != 0);
        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 208 ms 86352 KB Output is correct
2 Correct 79 ms 12880 KB Output is correct
3 Correct 77 ms 13028 KB Output is correct
4 Correct 77 ms 13312 KB Output is correct
5 Correct 81 ms 13140 KB Output is correct
6 Correct 81 ms 12964 KB Output is correct
7 Correct 76 ms 12884 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 210 ms 86292 KB Output is correct
12 Correct 231 ms 86456 KB Output is correct
13 Correct 217 ms 86612 KB Output is correct
14 Correct 211 ms 86864 KB Output is correct
15 Correct 217 ms 86608 KB Output is correct
16 Correct 228 ms 86228 KB Output is correct
17 Correct 214 ms 86312 KB Output is correct
18 Correct 217 ms 86356 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 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 267 ms 93120 KB Output is correct
2 Correct 68 ms 12368 KB Output is correct
3 Correct 89 ms 12452 KB Output is correct
4 Correct 57 ms 12368 KB Output is correct
5 Correct 68 ms 12624 KB Output is correct
6 Correct 74 ms 12560 KB Output is correct
7 Correct 68 ms 12552 KB Output is correct
8 Correct 4 ms 9816 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9664 KB Output is correct
11 Correct 289 ms 91728 KB Output is correct
12 Correct 260 ms 92972 KB Output is correct
13 Correct 292 ms 91572 KB Output is correct
14 Correct 318 ms 91732 KB Output is correct
15 Correct 258 ms 93012 KB Output is correct
16 Correct 314 ms 93600 KB Output is correct
17 Correct 311 ms 93624 KB Output is correct
18 Correct 304 ms 93776 KB Output is correct
19 Correct 263 ms 92864 KB Output is correct
20 Correct 253 ms 93012 KB Output is correct
21 Correct 274 ms 92852 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 93120 KB Output is correct
2 Correct 68 ms 12368 KB Output is correct
3 Correct 89 ms 12452 KB Output is correct
4 Correct 57 ms 12368 KB Output is correct
5 Correct 68 ms 12624 KB Output is correct
6 Correct 74 ms 12560 KB Output is correct
7 Correct 68 ms 12552 KB Output is correct
8 Correct 4 ms 9816 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9664 KB Output is correct
11 Correct 289 ms 91728 KB Output is correct
12 Correct 260 ms 92972 KB Output is correct
13 Correct 292 ms 91572 KB Output is correct
14 Correct 318 ms 91732 KB Output is correct
15 Correct 258 ms 93012 KB Output is correct
16 Correct 314 ms 93600 KB Output is correct
17 Correct 311 ms 93624 KB Output is correct
18 Correct 304 ms 93776 KB Output is correct
19 Correct 263 ms 92864 KB Output is correct
20 Correct 253 ms 93012 KB Output is correct
21 Correct 274 ms 92852 KB Output is correct
22 Correct 527 ms 95320 KB Output is correct
23 Correct 103 ms 12880 KB Output is correct
24 Correct 91 ms 13120 KB Output is correct
25 Correct 92 ms 12884 KB Output is correct
26 Correct 96 ms 13136 KB Output is correct
27 Correct 97 ms 13140 KB Output is correct
28 Correct 96 ms 13136 KB Output is correct
29 Correct 4 ms 9816 KB Output is correct
30 Correct 4 ms 9784 KB Output is correct
31 Correct 4 ms 9820 KB Output is correct
32 Incorrect 535 ms 92516 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 86352 KB Output is correct
2 Correct 79 ms 12880 KB Output is correct
3 Correct 77 ms 13028 KB Output is correct
4 Correct 77 ms 13312 KB Output is correct
5 Correct 81 ms 13140 KB Output is correct
6 Correct 81 ms 12964 KB Output is correct
7 Correct 76 ms 12884 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 210 ms 86292 KB Output is correct
12 Correct 231 ms 86456 KB Output is correct
13 Correct 217 ms 86612 KB Output is correct
14 Correct 211 ms 86864 KB Output is correct
15 Correct 217 ms 86608 KB Output is correct
16 Correct 228 ms 86228 KB Output is correct
17 Correct 214 ms 86312 KB Output is correct
18 Correct 217 ms 86356 KB Output is correct
19 Incorrect 7 ms 9820 KB Output isn't correct
20 Halted 0 ms 0 KB -