oj.uz

Submission #747552

# Submission time Handle Problem Language Result Execution time Memory
747552 2023-05-24T10:12:54 Z baluteshih Mizuyokan 2 (JOI23_mizuyokan2) C++14
28 / 100
 4000 ms 522776 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;

        if (arr[x] != y) {
            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);
        }

        if (a + 1 == b) {
            cout << "1\n";
            continue;
        }

        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);
        }
        modify(a + 1, min(b - 1, a + C), 1);

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

        int ans = 1;
        Node res = query(a + 1, b - 1, 1);
        pii one = res.mx[1], two = res.mx[0];
        one.X += a + 1 - 1 - 1, one.Y -= 1;
        two.X += a + 1 - 0 - 1;
        ans = max({ans, one.Y + 1, two.Y + 1});
        if (lftb - 1 > one.X) one.Y += 2;
        if (lftb - 1 > two.X) two.Y += 2;
        ans = max({ans, one.Y, two.Y});

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

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 516876 KB Output is correct
2 Correct 226 ms 516888 KB Output is correct
3 Correct 244 ms 516996 KB Output is correct
4 Correct 234 ms 516920 KB Output is correct
5 Correct 231 ms 516924 KB Output is correct
6 Correct 235 ms 516880 KB Output is correct
7 Correct 239 ms 516884 KB Output is correct
8 Correct 239 ms 516832 KB Output is correct
9 Correct 239 ms 516856 KB Output is correct
10 Correct 239 ms 516884 KB Output is correct
11 Correct 234 ms 516852 KB Output is correct
12 Correct 232 ms 516948 KB Output is correct
13 Correct 240 ms 516944 KB Output is correct
14 Correct 236 ms 516944 KB Output is correct
15 Correct 244 ms 517008 KB Output is correct
16 Correct 235 ms 516944 KB Output is correct
17 Correct 240 ms 516960 KB Output is correct
18 Correct 239 ms 516968 KB Output is correct
19 Correct 236 ms 516940 KB Output is correct
20 Correct 240 ms 516940 KB Output is correct
21 Correct 241 ms 516968 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 516876 KB Output is correct
2 Correct 226 ms 516888 KB Output is correct
3 Correct 244 ms 516996 KB Output is correct
4 Correct 234 ms 516920 KB Output is correct
5 Correct 231 ms 516924 KB Output is correct
6 Correct 235 ms 516880 KB Output is correct
7 Correct 239 ms 516884 KB Output is correct
8 Correct 239 ms 516832 KB Output is correct
9 Correct 239 ms 516856 KB Output is correct
10 Correct 239 ms 516884 KB Output is correct
11 Correct 234 ms 516852 KB Output is correct
12 Correct 232 ms 516948 KB Output is correct
13 Correct 240 ms 516944 KB Output is correct
14 Correct 236 ms 516944 KB Output is correct
15 Correct 244 ms 517008 KB Output is correct
16 Correct 235 ms 516944 KB Output is correct
17 Correct 240 ms 516960 KB Output is correct
18 Correct 239 ms 516968 KB Output is correct
19 Correct 236 ms 516940 KB Output is correct
20 Correct 240 ms 516940 KB Output is correct
21 Correct 241 ms 516968 KB Output is correct
22 Correct 252 ms 516968 KB Output is correct
23 Correct 234 ms 516940 KB Output is correct
24 Correct 234 ms 516944 KB Output is correct
25 Correct 230 ms 516920 KB Output is correct
26 Correct 237 ms 517004 KB Output is correct
27 Correct 244 ms 516916 KB Output is correct
28 Correct 238 ms 516940 KB Output is correct
29 Correct 240 ms 516936 KB Output is correct
30 Correct 237 ms 516940 KB Output is correct
31 Correct 248 ms 517092 KB Output is correct
32 Correct 239 ms 517008 KB Output is correct
33 Correct 234 ms 516916 KB Output is correct
34 Correct 249 ms 517072 KB Output is correct
35 Correct 240 ms 516940 KB Output is correct
36 Correct 241 ms 516872 KB Output is correct
37 Correct 237 ms 516976 KB Output is correct
38 Correct 234 ms 517020 KB Output is correct
39 Correct 239 ms 516940 KB Output is correct
40 Correct 247 ms 517116 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 516876 KB Output is correct
2 Correct 226 ms 516888 KB Output is correct
3 Correct 244 ms 516996 KB Output is correct
4 Correct 234 ms 516920 KB Output is correct
5 Correct 231 ms 516924 KB Output is correct
6 Correct 235 ms 516880 KB Output is correct
7 Correct 239 ms 516884 KB Output is correct
8 Correct 239 ms 516832 KB Output is correct
9 Correct 239 ms 516856 KB Output is correct
10 Correct 239 ms 516884 KB Output is correct
11 Correct 234 ms 516852 KB Output is correct
12 Correct 232 ms 516948 KB Output is correct
13 Correct 240 ms 516944 KB Output is correct
14 Correct 236 ms 516944 KB Output is correct
15 Correct 244 ms 517008 KB Output is correct
16 Correct 235 ms 516944 KB Output is correct
17 Correct 240 ms 516960 KB Output is correct
18 Correct 239 ms 516968 KB Output is correct
19 Correct 236 ms 516940 KB Output is correct
20 Correct 240 ms 516940 KB Output is correct
21 Correct 241 ms 516968 KB Output is correct
22 Correct 252 ms 516968 KB Output is correct
23 Correct 234 ms 516940 KB Output is correct
24 Correct 234 ms 516944 KB Output is correct
25 Correct 230 ms 516920 KB Output is correct
26 Correct 237 ms 517004 KB Output is correct
27 Correct 244 ms 516916 KB Output is correct
28 Correct 238 ms 516940 KB Output is correct
29 Correct 240 ms 516936 KB Output is correct
30 Correct 237 ms 516940 KB Output is correct
31 Correct 248 ms 517092 KB Output is correct
32 Correct 239 ms 517008 KB Output is correct
33 Correct 234 ms 516916 KB Output is correct
34 Correct 249 ms 517072 KB Output is correct
35 Correct 240 ms 516940 KB Output is correct
36 Correct 241 ms 516872 KB Output is correct
37 Correct 237 ms 516976 KB Output is correct
38 Correct 234 ms 517020 KB Output is correct
39 Correct 239 ms 516940 KB Output is correct
40 Correct 247 ms 517116 KB Output is correct
41 Correct 370 ms 520732 KB Output is correct
42 Correct 365 ms 521020 KB Output is correct
43 Correct 355 ms 520856 KB Output is correct
44 Correct 326 ms 519880 KB Output is correct
45 Correct 361 ms 521232 KB Output is correct
46 Correct 362 ms 520296 KB Output is correct
47 Correct 334 ms 519864 KB Output is correct
48 Correct 381 ms 520572 KB Output is correct
49 Correct 367 ms 520432 KB Output is correct
50 Correct 366 ms 520376 KB Output is correct
51 Correct 374 ms 520500 KB Output is correct
52 Correct 407 ms 520204 KB Output is correct
53 Correct 382 ms 521284 KB Output is correct
54 Correct 359 ms 520272 KB Output is correct
55 Correct 353 ms 520284 KB Output is correct
56 Correct 383 ms 520304 KB Output is correct
57 Correct 357 ms 520308 KB Output is correct
58 Correct 375 ms 520376 KB Output is correct
59 Correct 359 ms 521316 KB Output is correct
60 Correct 389 ms 521356 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 516892 KB Output is correct
2 Correct 2745 ms 521532 KB Output is correct
3 Correct 3517 ms 522388 KB Output is correct
4 Correct 3513 ms 522124 KB Output is correct
5 Correct 2744 ms 520800 KB Output is correct
6 Correct 3559 ms 520940 KB Output is correct
7 Correct 3566 ms 521892 KB Output is correct
8 Correct 3565 ms 521924 KB Output is correct
9 Correct 3561 ms 521924 KB Output is correct
10 Correct 3383 ms 521052 KB Output is correct
11 Correct 3629 ms 521984 KB Output is correct
12 Correct 3680 ms 521964 KB Output is correct
13 Correct 3602 ms 521968 KB Output is correct
14 Correct 3884 ms 521920 KB Output is correct
15 Execution timed out 4115 ms 522776 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 516856 KB Output is correct
2 Correct 273 ms 516876 KB Output is correct
3 Execution timed out 4070 ms 521740 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 516876 KB Output is correct
2 Correct 226 ms 516888 KB Output is correct
3 Correct 244 ms 516996 KB Output is correct
4 Correct 234 ms 516920 KB Output is correct
5 Correct 231 ms 516924 KB Output is correct
6 Correct 235 ms 516880 KB Output is correct
7 Correct 239 ms 516884 KB Output is correct
8 Correct 239 ms 516832 KB Output is correct
9 Correct 239 ms 516856 KB Output is correct
10 Correct 239 ms 516884 KB Output is correct
11 Correct 234 ms 516852 KB Output is correct
12 Correct 232 ms 516948 KB Output is correct
13 Correct 240 ms 516944 KB Output is correct
14 Correct 236 ms 516944 KB Output is correct
15 Correct 244 ms 517008 KB Output is correct
16 Correct 235 ms 516944 KB Output is correct
17 Correct 240 ms 516960 KB Output is correct
18 Correct 239 ms 516968 KB Output is correct
19 Correct 236 ms 516940 KB Output is correct
20 Correct 240 ms 516940 KB Output is correct
21 Correct 241 ms 516968 KB Output is correct
22 Correct 252 ms 516968 KB Output is correct
23 Correct 234 ms 516940 KB Output is correct
24 Correct 234 ms 516944 KB Output is correct
25 Correct 230 ms 516920 KB Output is correct
26 Correct 237 ms 517004 KB Output is correct
27 Correct 244 ms 516916 KB Output is correct
28 Correct 238 ms 516940 KB Output is correct
29 Correct 240 ms 516936 KB Output is correct
30 Correct 237 ms 516940 KB Output is correct
31 Correct 248 ms 517092 KB Output is correct
32 Correct 239 ms 517008 KB Output is correct
33 Correct 234 ms 516916 KB Output is correct
34 Correct 249 ms 517072 KB Output is correct
35 Correct 240 ms 516940 KB Output is correct
36 Correct 241 ms 516872 KB Output is correct
37 Correct 237 ms 516976 KB Output is correct
38 Correct 234 ms 517020 KB Output is correct
39 Correct 239 ms 516940 KB Output is correct
40 Correct 247 ms 517116 KB Output is correct
41 Correct 370 ms 520732 KB Output is correct
42 Correct 365 ms 521020 KB Output is correct
43 Correct 355 ms 520856 KB Output is correct
44 Correct 326 ms 519880 KB Output is correct
45 Correct 361 ms 521232 KB Output is correct
46 Correct 362 ms 520296 KB Output is correct
47 Correct 334 ms 519864 KB Output is correct
48 Correct 381 ms 520572 KB Output is correct
49 Correct 367 ms 520432 KB Output is correct
50 Correct 366 ms 520376 KB Output is correct
51 Correct 374 ms 520500 KB Output is correct
52 Correct 407 ms 520204 KB Output is correct
53 Correct 382 ms 521284 KB Output is correct
54 Correct 359 ms 520272 KB Output is correct
55 Correct 353 ms 520284 KB Output is correct
56 Correct 383 ms 520304 KB Output is correct
57 Correct 357 ms 520308 KB Output is correct
58 Correct 375 ms 520376 KB Output is correct
59 Correct 359 ms 521316 KB Output is correct
60 Correct 389 ms 521356 KB Output is correct
61 Correct 252 ms 516892 KB Output is correct
62 Correct 2745 ms 521532 KB Output is correct
63 Correct 3517 ms 522388 KB Output is correct
64 Correct 3513 ms 522124 KB Output is correct
65 Correct 2744 ms 520800 KB Output is correct
66 Correct 3559 ms 520940 KB Output is correct
67 Correct 3566 ms 521892 KB Output is correct
68 Correct 3565 ms 521924 KB Output is correct
69 Correct 3561 ms 521924 KB Output is correct
70 Correct 3383 ms 521052 KB Output is correct
71 Correct 3629 ms 521984 KB Output is correct
72 Correct 3680 ms 521964 KB Output is correct
73 Correct 3602 ms 521968 KB Output is correct
74 Correct 3884 ms 521920 KB Output is correct
75 Execution timed out 4115 ms 522776 KB Time limit exceeded
76 Halted 0 ms 0 KB -