oj.uz

Submission #1093406

# Submission time Handle Problem Language Result Execution time Memory
1093406 2024-09-26T18:39:25 Z vyshniak_n Progression (NOI20_progression) C++17
61 / 100
 3000 ms 95996 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 = 1e9 + 7;
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 = valr = x;
        sum_d = len * x;
    }

    node(node ql, node qr) {
        sum = 0;
        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;

            for (ll i = l; i <= r; i++)
                d[i] += s, s += c;
        } 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 != 1) vall = d[l - 1];
            if (r != n) valr = d[r + 1];
            /*
            if (l != 1 && d[l - 1] != vall)
                return void(cout << 1 / 0 << el);
            if (r != n && d[r + 1] != valr)
                return void(cout << 1 / 0 << el);
            */

            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, r + 1, r + 1, valr - (s + (r - l) * c));
            if (l == 1)
                f = s;
            for (ll i = l; i <= r; i++)
                d[i] = s, s += 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:259:20: warning: 'valr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  259 |                 upd(1, 1, n, r + 1, r + 1, valr - (s + (r - l) * c));
      |                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:257:20: warning: 'vall' may be used uninitialized in this function [-Wmaybe-uninitialized]
  257 |                 upd(1, 1, n, l, l, s - vall);
      |                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3038 ms 77904 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 4 ms 9892 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 3 ms 9740 KB Output is correct
7 Correct 4 ms 9816 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 6 ms 9980 KB Output is correct
11 Correct 5 ms 9820 KB Output is correct
12 Correct 5 ms 9828 KB Output is correct
13 Correct 6 ms 9820 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Correct 5 ms 10068 KB Output is correct
16 Correct 5 ms 9820 KB Output is correct
17 Correct 5 ms 9820 KB Output is correct
18 Correct 6 ms 10332 KB Output is correct
19 Correct 6 ms 9820 KB Output is correct
20 Correct 4 ms 9820 KB Output is correct
21 Correct 6 ms 9820 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 86872 KB Output is correct
2 Correct 68 ms 10320 KB Output is correct
3 Correct 66 ms 10320 KB Output is correct
4 Correct 55 ms 10320 KB Output is correct
5 Correct 67 ms 10320 KB Output is correct
6 Correct 70 ms 10520 KB Output is correct
7 Correct 66 ms 10324 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 286 ms 86824 KB Output is correct
12 Correct 272 ms 86996 KB Output is correct
13 Correct 300 ms 86868 KB Output is correct
14 Correct 290 ms 86864 KB Output is correct
15 Correct 263 ms 87012 KB Output is correct
16 Correct 289 ms 87380 KB Output is correct
17 Correct 306 ms 87376 KB Output is correct
18 Correct 298 ms 87380 KB Output is correct
19 Correct 258 ms 86656 KB Output is correct
20 Correct 275 ms 86608 KB Output is correct
21 Correct 264 ms 86608 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 86268 KB Output is correct
2 Correct 87 ms 13120 KB Output is correct
3 Correct 89 ms 13228 KB Output is correct
4 Correct 96 ms 12976 KB Output is correct
5 Correct 89 ms 13072 KB Output is correct
6 Correct 91 ms 13232 KB Output is correct
7 Correct 91 ms 13140 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 440 ms 92500 KB Output is correct
12 Correct 421 ms 95880 KB Output is correct
13 Correct 430 ms 92504 KB Output is correct
14 Correct 446 ms 92500 KB Output is correct
15 Correct 400 ms 95824 KB Output is correct
16 Correct 442 ms 95832 KB Output is correct
17 Correct 478 ms 95816 KB Output is correct
18 Correct 425 ms 95996 KB Output is correct
19 Correct 405 ms 95824 KB Output is correct
20 Correct 404 ms 95828 KB Output is correct
21 Correct 430 ms 95840 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 86872 KB Output is correct
2 Correct 68 ms 10320 KB Output is correct
3 Correct 66 ms 10320 KB Output is correct
4 Correct 55 ms 10320 KB Output is correct
5 Correct 67 ms 10320 KB Output is correct
6 Correct 70 ms 10520 KB Output is correct
7 Correct 66 ms 10324 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 286 ms 86824 KB Output is correct
12 Correct 272 ms 86996 KB Output is correct
13 Correct 300 ms 86868 KB Output is correct
14 Correct 290 ms 86864 KB Output is correct
15 Correct 263 ms 87012 KB Output is correct
16 Correct 289 ms 87380 KB Output is correct
17 Correct 306 ms 87376 KB Output is correct
18 Correct 298 ms 87380 KB Output is correct
19 Correct 258 ms 86656 KB Output is correct
20 Correct 275 ms 86608 KB Output is correct
21 Correct 264 ms 86608 KB Output is correct
22 Execution timed out 3040 ms 86472 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3038 ms 77904 KB Time limit exceeded
2 Halted 0 ms 0 KB -