oj.uz

Submission #1093369

# Submission time Handle Problem Language Result Execution time Memory
1093369 2024-09-26T17:51:58 Z vyshniak_n Progression (NOI20_progression) C++17
0 / 100
 517 ms 95824 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(r, 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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 86356 KB Output is correct
2 Correct 77 ms 13024 KB Output is correct
3 Correct 81 ms 13024 KB Output is correct
4 Correct 77 ms 12884 KB Output is correct
5 Correct 77 ms 13028 KB Output is correct
6 Correct 84 ms 13136 KB Output is correct
7 Correct 81 ms 12884 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 5 ms 9704 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 219 ms 86412 KB Output is correct
12 Correct 205 ms 86356 KB Output is correct
13 Correct 220 ms 86868 KB Output is correct
14 Correct 204 ms 86864 KB Output is correct
15 Correct 207 ms 86712 KB Output is correct
16 Incorrect 205 ms 86352 KB Output isn't correct
17 Halted 0 ms 0 KB -

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
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 92904 KB Output is correct
2 Correct 70 ms 12368 KB Output is correct
3 Correct 65 ms 12372 KB Output is correct
4 Correct 55 ms 12352 KB Output is correct
5 Correct 67 ms 12596 KB Output is correct
6 Correct 71 ms 12632 KB Output is correct
7 Correct 69 ms 12712 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 9692 KB Output is correct
11 Incorrect 293 ms 91964 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 92904 KB Output is correct
2 Correct 70 ms 12368 KB Output is correct
3 Correct 65 ms 12372 KB Output is correct
4 Correct 55 ms 12352 KB Output is correct
5 Correct 67 ms 12596 KB Output is correct
6 Correct 71 ms 12632 KB Output is correct
7 Correct 69 ms 12712 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 9692 KB Output is correct
11 Incorrect 293 ms 91964 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 86356 KB Output is correct
2 Correct 77 ms 13024 KB Output is correct
3 Correct 81 ms 13024 KB Output is correct
4 Correct 77 ms 12884 KB Output is correct
5 Correct 77 ms 13028 KB Output is correct
6 Correct 84 ms 13136 KB Output is correct
7 Correct 81 ms 12884 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 5 ms 9704 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 219 ms 86412 KB Output is correct
12 Correct 205 ms 86356 KB Output is correct
13 Correct 220 ms 86868 KB Output is correct
14 Correct 204 ms 86864 KB Output is correct
15 Correct 207 ms 86712 KB Output is correct
16 Incorrect 205 ms 86352 KB Output isn't correct
17 Halted 0 ms 0 KB -