oj.uz

답안 #1093384

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1093384 2024-09-26T18:20:39 Z vyshniak_n Progression (NOI20_progression) C++17
35 / 100
 3000 ms 160336 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 && 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:246:39: warning: division by zero [-Wdiv-by-zero]
  246 |                 return void(cout << 1 / 0 << el);
      |                                     ~~^~~
Progression.cpp:248:39: warning: division by zero [-Wdiv-by-zero]
  248 |                 return void(cout << 1 / 0 << el);
      |                                     ~~^~~
Progression.cpp:256:20: warning: 'valr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  256 |                 upd(1, 1, n, l, l, valr - (s + (r - l) * c));
      |                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:245:24: warning: 'vall' may be used uninitialized in this function [-Wmaybe-uninitialized]
  245 |             if (l != 1 && d[l - 1] != vall)
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3050 ms 81244 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 19804 KB Execution killed with signal 4
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 265 ms 93008 KB Output is correct
2 Correct 66 ms 12356 KB Output is correct
3 Correct 64 ms 12368 KB Output is correct
4 Correct 56 ms 12372 KB Output is correct
5 Correct 65 ms 12628 KB Output is correct
6 Correct 66 ms 12504 KB Output is correct
7 Correct 67 ms 12624 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 9748 KB Output is correct
11 Correct 310 ms 91564 KB Output is correct
12 Correct 267 ms 93180 KB Output is correct
13 Correct 316 ms 91732 KB Output is correct
14 Correct 292 ms 91756 KB Output is correct
15 Correct 293 ms 93008 KB Output is correct
16 Correct 285 ms 93520 KB Output is correct
17 Correct 280 ms 93600 KB Output is correct
18 Correct 289 ms 93776 KB Output is correct
19 Correct 253 ms 93144 KB Output is correct
20 Correct 262 ms 92984 KB Output is correct
21 Correct 251 ms 93076 KB Output is correct

Subtask #4
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 138 ms 160336 KB Execution killed with signal 4
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 265 ms 93008 KB Output is correct
2 Correct 66 ms 12356 KB Output is correct
3 Correct 64 ms 12368 KB Output is correct
4 Correct 56 ms 12372 KB Output is correct
5 Correct 65 ms 12628 KB Output is correct
6 Correct 66 ms 12504 KB Output is correct
7 Correct 67 ms 12624 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 9748 KB Output is correct
11 Correct 310 ms 91564 KB Output is correct
12 Correct 267 ms 93180 KB Output is correct
13 Correct 316 ms 91732 KB Output is correct
14 Correct 292 ms 91756 KB Output is correct
15 Correct 293 ms 93008 KB Output is correct
16 Correct 285 ms 93520 KB Output is correct
17 Correct 280 ms 93600 KB Output is correct
18 Correct 289 ms 93776 KB Output is correct
19 Correct 253 ms 93144 KB Output is correct
20 Correct 262 ms 92984 KB Output is correct
21 Correct 251 ms 93076 KB Output is correct
22 Execution timed out 3037 ms 92892 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3050 ms 81244 KB Time limit exceeded
2 Halted 0 ms 0 KB -