oj.uz

Submission #747545

# Submission time Handle Problem Language Result Execution time Memory
747545 2023-05-24T09:58:42 Z baluteshih Mizuyokan 2 (JOI23_mizuyokan2) C++14
28 / 100
 4000 ms 519832 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back

const int C = 64;

pii operator+(const pii &a, const pii &b) { return pii(a.X + b.X, a.Y + b.Y); }

int arr[250005], lft[250005], tmp[250005];

struct Node {
    int l, r;
    pii mx[C + 1]; // mx[i]: start with (l - i - 1, 0), jump to (i + mx[i].X, mx[i].Y)
    Node() {}
    Node(int v): l(v), r(v) {   
        for (int i = 0; i <= C; ++i) {
            mx[i] = pii(0, 0);
            if (lft[v] - 1 > v - i - 1) mx[i] = pii(i + 1, 2);
        }
    }
    Node operator+(const Node &a) const {
        Node res(*this);
        res.r = a.r;
        for (int i = 0; i <= C; ++i) {
            if (res.l - i - 1 + res.mx[i].X < a.l - C - 1) res.mx[i] = res.mx[i] + a.mx[C];
            else res.mx[i] = res.mx[i] + a.mx[a.l - (res.l - i - 1 + res.mx[i].X) - 1];
        }
        return res;
    }
} seg[1000005];

void build(int l, int r, int rt) {
    if (l == r) return seg[rt] = Node(l), void();
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1), build(mid + 1, r, rt << 1 | 1);
    seg[rt] = seg[rt << 1] + seg[rt << 1 | 1];
}

void modify(int L, int R, int rt) {
    if (seg[rt].l == seg[rt].r) return seg[rt] = Node(seg[rt].l), void();
    int mid = (seg[rt].l + seg[rt].r) >> 1;
    if (L <= mid) modify(L, R, rt << 1);
    if (R > mid) modify(L, R, rt << 1 | 1);
    seg[rt] = seg[rt << 1] + seg[rt << 1 | 1];
}

Node query(int L, int R, int rt) {
    if (L <= seg[rt].l && R >= seg[rt].r) return seg[rt];
    int mid = (seg[rt].l + seg[rt].r) >> 1;
    if (R <= mid) return query(L, R, rt << 1);
    if (L > mid) return query(L, R, rt << 1 | 1);
    return query(L, R, rt << 1) + query(L, R, rt << 1 | 1);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> arr[i];
    
    auto update = [&](int i) {
        lft[i] = -C - 1;
        ll cur = 0;
        for (int j = i; j > 0 && j > i - C; --j) {
            cur += arr[j];
            if (cur > max(arr[j - 1], arr[i + 1])) {
                lft[i] = j;
                break;
            }
        }
    };

    for (int i = 1; i <= n; ++i)
        update(i);

    build(1, n, 1);

    int q;
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        int x, y, a, b;
        cin >> x >> y >> a >> b;

        arr[x] = y;
        for (int j = max(1, x - 1); j <= n && j <= x + C; ++j)
            update(j);
        modify(max(1, x - 1), min(n, x + C), 1);
        
        ll cur = 0;
        for (int j = a + 1; j < b && j <= a + C; ++j) {
            tmp[j] = lft[j];
            cur += arr[j];
            if (cur > arr[j + 1]) lft[j] = max(lft[j], a + 1);
        }
        if (a + 1 <= min(b - 1, a + C))
            modify(a + 1, min(b - 1, a + C), 1);

        tmp[b] = lft[b], lft[b] = 0, cur = 0;
        for (int j = b; j > a && j > b - C; --j) {
            cur += arr[j];
            if (j == a + 1 || cur > arr[j - 1]) {
                lft[b] = j;
                break;
            }
        }
        modify(b, b, 1);

        int ans = 1;
        Node res = query(a + 1, b, 1);
        if (res.mx[1].X + a + 1 - 1 - 1 == b) ans = max(ans, res.mx[1].Y - 1);
        else ans = max(ans, res.mx[1].Y);
        if (res.mx[0].X + a + 1 - 0 - 1 == b) ans = max(ans, res.mx[0].Y);
        else ans = max(ans, res.mx[0].Y + 1);

        for (int j = a + 1; j < b && j <= a + C; ++j)
            lft[j] = tmp[j];
        if (a + 1 <= min(b - 1, a + C))
            modify(a + 1, min(b - 1, a + C), 1);
        lft[b] = tmp[b];
        modify(b, b, 1);

        cout << ans << "\n";
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 517028 KB Output is correct
2 Correct 232 ms 516904 KB Output is correct
3 Correct 232 ms 516888 KB Output is correct
4 Correct 238 ms 516944 KB Output is correct
5 Correct 233 ms 516984 KB Output is correct
6 Correct 232 ms 516868 KB Output is correct
7 Correct 245 ms 516868 KB Output is correct
8 Correct 236 ms 516992 KB Output is correct
9 Correct 235 ms 516832 KB Output is correct
10 Correct 234 ms 516920 KB Output is correct
11 Correct 240 ms 516892 KB Output is correct
12 Correct 249 ms 516844 KB Output is correct
13 Correct 230 ms 516876 KB Output is correct
14 Correct 235 ms 516936 KB Output is correct
15 Correct 234 ms 516940 KB Output is correct
16 Correct 231 ms 516936 KB Output is correct
17 Correct 240 ms 516940 KB Output is correct
18 Correct 234 ms 516860 KB Output is correct
19 Correct 236 ms 516940 KB Output is correct
20 Correct 250 ms 516948 KB Output is correct
21 Correct 235 ms 516992 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 517028 KB Output is correct
2 Correct 232 ms 516904 KB Output is correct
3 Correct 232 ms 516888 KB Output is correct
4 Correct 238 ms 516944 KB Output is correct
5 Correct 233 ms 516984 KB Output is correct
6 Correct 232 ms 516868 KB Output is correct
7 Correct 245 ms 516868 KB Output is correct
8 Correct 236 ms 516992 KB Output is correct
9 Correct 235 ms 516832 KB Output is correct
10 Correct 234 ms 516920 KB Output is correct
11 Correct 240 ms 516892 KB Output is correct
12 Correct 249 ms 516844 KB Output is correct
13 Correct 230 ms 516876 KB Output is correct
14 Correct 235 ms 516936 KB Output is correct
15 Correct 234 ms 516940 KB Output is correct
16 Correct 231 ms 516936 KB Output is correct
17 Correct 240 ms 516940 KB Output is correct
18 Correct 234 ms 516860 KB Output is correct
19 Correct 236 ms 516940 KB Output is correct
20 Correct 250 ms 516948 KB Output is correct
21 Correct 235 ms 516992 KB Output is correct
22 Correct 236 ms 516860 KB Output is correct
23 Correct 261 ms 517076 KB Output is correct
24 Correct 238 ms 516928 KB Output is correct
25 Correct 240 ms 517000 KB Output is correct
26 Correct 234 ms 516984 KB Output is correct
27 Correct 242 ms 516984 KB Output is correct
28 Correct 237 ms 517092 KB Output is correct
29 Correct 233 ms 516888 KB Output is correct
30 Correct 239 ms 517028 KB Output is correct
31 Correct 242 ms 516916 KB Output is correct
32 Correct 233 ms 516972 KB Output is correct
33 Correct 238 ms 516980 KB Output is correct
34 Correct 252 ms 516976 KB Output is correct
35 Correct 240 ms 516940 KB Output is correct
36 Correct 244 ms 516972 KB Output is correct
37 Correct 246 ms 516876 KB Output is correct
38 Correct 237 ms 517084 KB Output is correct
39 Correct 242 ms 516920 KB Output is correct
40 Correct 267 ms 516968 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 517028 KB Output is correct
2 Correct 232 ms 516904 KB Output is correct
3 Correct 232 ms 516888 KB Output is correct
4 Correct 238 ms 516944 KB Output is correct
5 Correct 233 ms 516984 KB Output is correct
6 Correct 232 ms 516868 KB Output is correct
7 Correct 245 ms 516868 KB Output is correct
8 Correct 236 ms 516992 KB Output is correct
9 Correct 235 ms 516832 KB Output is correct
10 Correct 234 ms 516920 KB Output is correct
11 Correct 240 ms 516892 KB Output is correct
12 Correct 249 ms 516844 KB Output is correct
13 Correct 230 ms 516876 KB Output is correct
14 Correct 235 ms 516936 KB Output is correct
15 Correct 234 ms 516940 KB Output is correct
16 Correct 231 ms 516936 KB Output is correct
17 Correct 240 ms 516940 KB Output is correct
18 Correct 234 ms 516860 KB Output is correct
19 Correct 236 ms 516940 KB Output is correct
20 Correct 250 ms 516948 KB Output is correct
21 Correct 235 ms 516992 KB Output is correct
22 Correct 236 ms 516860 KB Output is correct
23 Correct 261 ms 517076 KB Output is correct
24 Correct 238 ms 516928 KB Output is correct
25 Correct 240 ms 517000 KB Output is correct
26 Correct 234 ms 516984 KB Output is correct
27 Correct 242 ms 516984 KB Output is correct
28 Correct 237 ms 517092 KB Output is correct
29 Correct 233 ms 516888 KB Output is correct
30 Correct 239 ms 517028 KB Output is correct
31 Correct 242 ms 516916 KB Output is correct
32 Correct 233 ms 516972 KB Output is correct
33 Correct 238 ms 516980 KB Output is correct
34 Correct 252 ms 516976 KB Output is correct
35 Correct 240 ms 516940 KB Output is correct
36 Correct 244 ms 516972 KB Output is correct
37 Correct 246 ms 516876 KB Output is correct
38 Correct 237 ms 517084 KB Output is correct
39 Correct 242 ms 516920 KB Output is correct
40 Correct 267 ms 516968 KB Output is correct
41 Correct 364 ms 518680 KB Output is correct
42 Correct 372 ms 518944 KB Output is correct
43 Correct 369 ms 518928 KB Output is correct
44 Correct 344 ms 518248 KB Output is correct
45 Correct 365 ms 518908 KB Output is correct
46 Correct 373 ms 518908 KB Output is correct
47 Correct 341 ms 518416 KB Output is correct
48 Correct 369 ms 518912 KB Output is correct
49 Correct 365 ms 518952 KB Output is correct
50 Correct 373 ms 518912 KB Output is correct
51 Correct 367 ms 518908 KB Output is correct
52 Correct 352 ms 518432 KB Output is correct
53 Correct 371 ms 518956 KB Output is correct
54 Correct 356 ms 519120 KB Output is correct
55 Correct 357 ms 518944 KB Output is correct
56 Correct 361 ms 518940 KB Output is correct
57 Correct 358 ms 518988 KB Output is correct
58 Correct 369 ms 518932 KB Output is correct
59 Correct 370 ms 519016 KB Output is correct
60 Correct 376 ms 519032 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 516876 KB Output is correct
2 Execution timed out 4122 ms 519252 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 517016 KB Output is correct
2 Correct 241 ms 516832 KB Output is correct
3 Execution timed out 4110 ms 519832 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 517028 KB Output is correct
2 Correct 232 ms 516904 KB Output is correct
3 Correct 232 ms 516888 KB Output is correct
4 Correct 238 ms 516944 KB Output is correct
5 Correct 233 ms 516984 KB Output is correct
6 Correct 232 ms 516868 KB Output is correct
7 Correct 245 ms 516868 KB Output is correct
8 Correct 236 ms 516992 KB Output is correct
9 Correct 235 ms 516832 KB Output is correct
10 Correct 234 ms 516920 KB Output is correct
11 Correct 240 ms 516892 KB Output is correct
12 Correct 249 ms 516844 KB Output is correct
13 Correct 230 ms 516876 KB Output is correct
14 Correct 235 ms 516936 KB Output is correct
15 Correct 234 ms 516940 KB Output is correct
16 Correct 231 ms 516936 KB Output is correct
17 Correct 240 ms 516940 KB Output is correct
18 Correct 234 ms 516860 KB Output is correct
19 Correct 236 ms 516940 KB Output is correct
20 Correct 250 ms 516948 KB Output is correct
21 Correct 235 ms 516992 KB Output is correct
22 Correct 236 ms 516860 KB Output is correct
23 Correct 261 ms 517076 KB Output is correct
24 Correct 238 ms 516928 KB Output is correct
25 Correct 240 ms 517000 KB Output is correct
26 Correct 234 ms 516984 KB Output is correct
27 Correct 242 ms 516984 KB Output is correct
28 Correct 237 ms 517092 KB Output is correct
29 Correct 233 ms 516888 KB Output is correct
30 Correct 239 ms 517028 KB Output is correct
31 Correct 242 ms 516916 KB Output is correct
32 Correct 233 ms 516972 KB Output is correct
33 Correct 238 ms 516980 KB Output is correct
34 Correct 252 ms 516976 KB Output is correct
35 Correct 240 ms 516940 KB Output is correct
36 Correct 244 ms 516972 KB Output is correct
37 Correct 246 ms 516876 KB Output is correct
38 Correct 237 ms 517084 KB Output is correct
39 Correct 242 ms 516920 KB Output is correct
40 Correct 267 ms 516968 KB Output is correct
41 Correct 364 ms 518680 KB Output is correct
42 Correct 372 ms 518944 KB Output is correct
43 Correct 369 ms 518928 KB Output is correct
44 Correct 344 ms 518248 KB Output is correct
45 Correct 365 ms 518908 KB Output is correct
46 Correct 373 ms 518908 KB Output is correct
47 Correct 341 ms 518416 KB Output is correct
48 Correct 369 ms 518912 KB Output is correct
49 Correct 365 ms 518952 KB Output is correct
50 Correct 373 ms 518912 KB Output is correct
51 Correct 367 ms 518908 KB Output is correct
52 Correct 352 ms 518432 KB Output is correct
53 Correct 371 ms 518956 KB Output is correct
54 Correct 356 ms 519120 KB Output is correct
55 Correct 357 ms 518944 KB Output is correct
56 Correct 361 ms 518940 KB Output is correct
57 Correct 358 ms 518988 KB Output is correct
58 Correct 369 ms 518932 KB Output is correct
59 Correct 370 ms 519016 KB Output is correct
60 Correct 376 ms 519032 KB Output is correct
61 Correct 239 ms 516876 KB Output is correct
62 Execution timed out 4122 ms 519252 KB Time limit exceeded
63 Halted 0 ms 0 KB -