oj.uz

Submission #1093405

# Submission time Handle Problem Language Result Execution time Memory
1093405 2024-09-26T18:38:44 Z vyshniak_n Progression (NOI20_progression) C++17
35 / 100
 3000 ms 87436 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, l, l, 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:260:20: warning: 'valr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  260 |                 upd(1, 1, n, l, l, valr - (s + (r - l) * c));
      |                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:258:20: warning: 'vall' may be used uninitialized in this function [-Wmaybe-uninitialized]
  258 |                 upd(1, 1, n, l, l, s - vall);
      |                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9816 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 255 ms 87004 KB Output is correct
2 Correct 67 ms 10284 KB Output is correct
3 Correct 66 ms 10324 KB Output is correct
4 Correct 53 ms 10320 KB Output is correct
5 Correct 66 ms 10332 KB Output is correct
6 Correct 68 ms 10320 KB Output is correct
7 Correct 65 ms 10456 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 3 ms 9820 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 276 ms 86656 KB Output is correct
12 Correct 247 ms 87120 KB Output is correct
13 Correct 292 ms 87088 KB Output is correct
14 Correct 302 ms 86856 KB Output is correct
15 Correct 251 ms 86868 KB Output is correct
16 Correct 304 ms 87380 KB Output is correct
17 Correct 284 ms 87376 KB Output is correct
18 Correct 302 ms 87436 KB Output is correct
19 Correct 263 ms 86608 KB Output is correct
20 Correct 265 ms 86612 KB Output is correct
21 Correct 264 ms 86540 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 423 ms 86128 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 87004 KB Output is correct
2 Correct 67 ms 10284 KB Output is correct
3 Correct 66 ms 10324 KB Output is correct
4 Correct 53 ms 10320 KB Output is correct
5 Correct 66 ms 10332 KB Output is correct
6 Correct 68 ms 10320 KB Output is correct
7 Correct 65 ms 10456 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 3 ms 9820 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 276 ms 86656 KB Output is correct
12 Correct 247 ms 87120 KB Output is correct
13 Correct 292 ms 87088 KB Output is correct
14 Correct 302 ms 86856 KB Output is correct
15 Correct 251 ms 86868 KB Output is correct
16 Correct 304 ms 87380 KB Output is correct
17 Correct 284 ms 87376 KB Output is correct
18 Correct 302 ms 87436 KB Output is correct
19 Correct 263 ms 86608 KB Output is correct
20 Correct 265 ms 86612 KB Output is correct
21 Correct 264 ms 86540 KB Output is correct
22 Execution timed out 3039 ms 86352 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 3067 ms 77908 KB Time limit exceeded
2 Halted 0 ms 0 KB -