oj.uz

Submission #1093347

# Submission time Handle Problem Language Result Execution time Memory
1093347 2024-09-26T16:57:37 Z vyshniak_n Progression (NOI20_progression) C++17
44 / 100
 535 ms 95936 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);

    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));
        } else if (t == 2) {
            cin >> l >> r >> s >> c;
            ll vall, valr;
            if (l != 1) vall = get_pos(1, 1, n, 2, l - 1);
            if (r != n) valr = 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));
        } 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:244:20: warning: 'valr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  244 |                 upd(1, 1, n, l, l, valr - (s + (r - l) * c));
      |                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:242:20: warning: 'vall' may be used uninitialized in this function [-Wmaybe-uninitialized]
  242 |                 upd(1, 1, n, l, l, s - vall);
      |                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 86356 KB Output is correct
2 Correct 78 ms 12880 KB Output is correct
3 Correct 78 ms 12880 KB Output is correct
4 Correct 79 ms 12880 KB Output is correct
5 Correct 79 ms 13140 KB Output is correct
6 Correct 79 ms 13140 KB Output is correct
7 Correct 78 ms 12880 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 3 ms 9820 KB Output is correct
11 Correct 223 ms 86340 KB Output is correct
12 Correct 220 ms 86368 KB Output is correct
13 Correct 229 ms 86552 KB Output is correct
14 Correct 230 ms 86868 KB Output is correct
15 Correct 222 ms 86544 KB Output is correct
16 Correct 228 ms 86456 KB Output is correct
17 Correct 218 ms 86356 KB Output is correct
18 Correct 225 ms 86352 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 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 276 ms 93016 KB Output is correct
2 Correct 70 ms 12464 KB Output is correct
3 Correct 71 ms 12332 KB Output is correct
4 Correct 55 ms 12456 KB Output is correct
5 Correct 67 ms 12624 KB Output is correct
6 Correct 67 ms 12548 KB Output is correct
7 Correct 68 ms 12488 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9816 KB Output is correct
11 Correct 311 ms 91684 KB Output is correct
12 Correct 289 ms 92992 KB Output is correct
13 Correct 302 ms 91728 KB Output is correct
14 Correct 313 ms 91568 KB Output is correct
15 Correct 270 ms 93008 KB Output is correct
16 Correct 304 ms 93520 KB Output is correct
17 Correct 308 ms 93524 KB Output is correct
18 Correct 293 ms 93776 KB Output is correct
19 Correct 276 ms 93028 KB Output is correct
20 Correct 275 ms 93012 KB Output is correct
21 Correct 283 ms 93012 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 93016 KB Output is correct
2 Correct 70 ms 12464 KB Output is correct
3 Correct 71 ms 12332 KB Output is correct
4 Correct 55 ms 12456 KB Output is correct
5 Correct 67 ms 12624 KB Output is correct
6 Correct 67 ms 12548 KB Output is correct
7 Correct 68 ms 12488 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9816 KB Output is correct
11 Correct 311 ms 91684 KB Output is correct
12 Correct 289 ms 92992 KB Output is correct
13 Correct 302 ms 91728 KB Output is correct
14 Correct 313 ms 91568 KB Output is correct
15 Correct 270 ms 93008 KB Output is correct
16 Correct 304 ms 93520 KB Output is correct
17 Correct 308 ms 93524 KB Output is correct
18 Correct 293 ms 93776 KB Output is correct
19 Correct 276 ms 93028 KB Output is correct
20 Correct 275 ms 93012 KB Output is correct
21 Correct 283 ms 93012 KB Output is correct
22 Correct 535 ms 95316 KB Output is correct
23 Correct 95 ms 13140 KB Output is correct
24 Correct 97 ms 12884 KB Output is correct
25 Correct 94 ms 12884 KB Output is correct
26 Correct 95 ms 13136 KB Output is correct
27 Correct 99 ms 13136 KB Output is correct
28 Correct 100 ms 13136 KB Output is correct
29 Correct 4 ms 9820 KB Output is correct
30 Correct 4 ms 9820 KB Output is correct
31 Correct 5 ms 9820 KB Output is correct
32 Incorrect 532 ms 92388 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 86356 KB Output is correct
2 Correct 78 ms 12880 KB Output is correct
3 Correct 78 ms 12880 KB Output is correct
4 Correct 79 ms 12880 KB Output is correct
5 Correct 79 ms 13140 KB Output is correct
6 Correct 79 ms 13140 KB Output is correct
7 Correct 78 ms 12880 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 3 ms 9820 KB Output is correct
11 Correct 223 ms 86340 KB Output is correct
12 Correct 220 ms 86368 KB Output is correct
13 Correct 229 ms 86552 KB Output is correct
14 Correct 230 ms 86868 KB Output is correct
15 Correct 222 ms 86544 KB Output is correct
16 Correct 228 ms 86456 KB Output is correct
17 Correct 218 ms 86356 KB Output is correct
18 Correct 225 ms 86352 KB Output is correct
19 Incorrect 6 ms 9820 KB Output isn't correct
20 Halted 0 ms 0 KB -