oj.uz

Submission #747553

# Submission time Handle Problem Language Result Execution time Memory
747553 2023-05-24T10:14:05 Z baluteshih Mizuyokan 2 (JOI23_mizuyokan2) C++14
60 / 100
 4000 ms 523932 KB 
#pragma GCC optimize("O3")
#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 257 ms 516844 KB Output is correct
2 Correct 236 ms 516832 KB Output is correct
3 Correct 249 ms 517024 KB Output is correct
4 Correct 240 ms 516948 KB Output is correct
5 Correct 250 ms 516912 KB Output is correct
6 Correct 236 ms 516852 KB Output is correct
7 Correct 258 ms 516936 KB Output is correct
8 Correct 230 ms 516988 KB Output is correct
9 Correct 235 ms 516944 KB Output is correct
10 Correct 238 ms 516880 KB Output is correct
11 Correct 229 ms 517112 KB Output is correct
12 Correct 242 ms 516940 KB Output is correct
13 Correct 249 ms 516880 KB Output is correct
14 Correct 226 ms 516944 KB Output is correct
15 Correct 239 ms 516952 KB Output is correct
16 Correct 243 ms 516932 KB Output is correct
17 Correct 245 ms 517012 KB Output is correct
18 Correct 262 ms 516940 KB Output is correct
19 Correct 239 ms 516936 KB Output is correct
20 Correct 231 ms 516992 KB Output is correct
21 Correct 237 ms 516980 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 516844 KB Output is correct
2 Correct 236 ms 516832 KB Output is correct
3 Correct 249 ms 517024 KB Output is correct
4 Correct 240 ms 516948 KB Output is correct
5 Correct 250 ms 516912 KB Output is correct
6 Correct 236 ms 516852 KB Output is correct
7 Correct 258 ms 516936 KB Output is correct
8 Correct 230 ms 516988 KB Output is correct
9 Correct 235 ms 516944 KB Output is correct
10 Correct 238 ms 516880 KB Output is correct
11 Correct 229 ms 517112 KB Output is correct
12 Correct 242 ms 516940 KB Output is correct
13 Correct 249 ms 516880 KB Output is correct
14 Correct 226 ms 516944 KB Output is correct
15 Correct 239 ms 516952 KB Output is correct
16 Correct 243 ms 516932 KB Output is correct
17 Correct 245 ms 517012 KB Output is correct
18 Correct 262 ms 516940 KB Output is correct
19 Correct 239 ms 516936 KB Output is correct
20 Correct 231 ms 516992 KB Output is correct
21 Correct 237 ms 516980 KB Output is correct
22 Correct 234 ms 516952 KB Output is correct
23 Correct 239 ms 517012 KB Output is correct
24 Correct 240 ms 516916 KB Output is correct
25 Correct 230 ms 516876 KB Output is correct
26 Correct 222 ms 516992 KB Output is correct
27 Correct 231 ms 516904 KB Output is correct
28 Correct 237 ms 516952 KB Output is correct
29 Correct 254 ms 516904 KB Output is correct
30 Correct 239 ms 516920 KB Output is correct
31 Correct 238 ms 516992 KB Output is correct
32 Correct 238 ms 516940 KB Output is correct
33 Correct 233 ms 517008 KB Output is correct
34 Correct 228 ms 516912 KB Output is correct
35 Correct 226 ms 517056 KB Output is correct
36 Correct 224 ms 516960 KB Output is correct
37 Correct 227 ms 516900 KB Output is correct
38 Correct 229 ms 517112 KB Output is correct
39 Correct 230 ms 516948 KB Output is correct
40 Correct 231 ms 516924 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 516844 KB Output is correct
2 Correct 236 ms 516832 KB Output is correct
3 Correct 249 ms 517024 KB Output is correct
4 Correct 240 ms 516948 KB Output is correct
5 Correct 250 ms 516912 KB Output is correct
6 Correct 236 ms 516852 KB Output is correct
7 Correct 258 ms 516936 KB Output is correct
8 Correct 230 ms 516988 KB Output is correct
9 Correct 235 ms 516944 KB Output is correct
10 Correct 238 ms 516880 KB Output is correct
11 Correct 229 ms 517112 KB Output is correct
12 Correct 242 ms 516940 KB Output is correct
13 Correct 249 ms 516880 KB Output is correct
14 Correct 226 ms 516944 KB Output is correct
15 Correct 239 ms 516952 KB Output is correct
16 Correct 243 ms 516932 KB Output is correct
17 Correct 245 ms 517012 KB Output is correct
18 Correct 262 ms 516940 KB Output is correct
19 Correct 239 ms 516936 KB Output is correct
20 Correct 231 ms 516992 KB Output is correct
21 Correct 237 ms 516980 KB Output is correct
22 Correct 234 ms 516952 KB Output is correct
23 Correct 239 ms 517012 KB Output is correct
24 Correct 240 ms 516916 KB Output is correct
25 Correct 230 ms 516876 KB Output is correct
26 Correct 222 ms 516992 KB Output is correct
27 Correct 231 ms 516904 KB Output is correct
28 Correct 237 ms 516952 KB Output is correct
29 Correct 254 ms 516904 KB Output is correct
30 Correct 239 ms 516920 KB Output is correct
31 Correct 238 ms 516992 KB Output is correct
32 Correct 238 ms 516940 KB Output is correct
33 Correct 233 ms 517008 KB Output is correct
34 Correct 228 ms 516912 KB Output is correct
35 Correct 226 ms 517056 KB Output is correct
36 Correct 224 ms 516960 KB Output is correct
37 Correct 227 ms 516900 KB Output is correct
38 Correct 229 ms 517112 KB Output is correct
39 Correct 230 ms 516948 KB Output is correct
40 Correct 231 ms 516924 KB Output is correct
41 Correct 312 ms 519440 KB Output is correct
42 Correct 315 ms 519624 KB Output is correct
43 Correct 324 ms 519752 KB Output is correct
44 Correct 296 ms 519048 KB Output is correct
45 Correct 342 ms 519684 KB Output is correct
46 Correct 328 ms 519716 KB Output is correct
47 Correct 306 ms 519244 KB Output is correct
48 Correct 327 ms 519712 KB Output is correct
49 Correct 333 ms 519672 KB Output is correct
50 Correct 334 ms 519692 KB Output is correct
51 Correct 332 ms 519704 KB Output is correct
52 Correct 303 ms 519224 KB Output is correct
53 Correct 327 ms 519692 KB Output is correct
54 Correct 315 ms 519676 KB Output is correct
55 Correct 315 ms 519780 KB Output is correct
56 Correct 316 ms 519680 KB Output is correct
57 Correct 326 ms 519756 KB Output is correct
58 Correct 326 ms 519700 KB Output is correct
59 Correct 337 ms 519704 KB Output is correct
60 Correct 315 ms 519684 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 517008 KB Output is correct
2 Correct 2142 ms 520172 KB Output is correct
3 Correct 2616 ms 521688 KB Output is correct
4 Correct 2721 ms 521596 KB Output is correct
5 Correct 2122 ms 522576 KB Output is correct
6 Correct 2741 ms 521736 KB Output is correct
7 Correct 2763 ms 521808 KB Output is correct
8 Correct 2743 ms 521576 KB Output is correct
9 Correct 2782 ms 521800 KB Output is correct
10 Correct 2662 ms 521240 KB Output is correct
11 Correct 2822 ms 521964 KB Output is correct
12 Correct 2765 ms 521892 KB Output is correct
13 Correct 2766 ms 521844 KB Output is correct
14 Correct 2823 ms 521188 KB Output is correct
15 Correct 2746 ms 520276 KB Output is correct
16 Correct 2782 ms 523012 KB Output is correct
17 Correct 1162 ms 523932 KB Output is correct
18 Correct 2677 ms 523580 KB Output is correct

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 516856 KB Output is correct
2 Correct 213 ms 516928 KB Output is correct
3 Correct 3104 ms 519964 KB Output is correct
4 Correct 3883 ms 522640 KB Output is correct
5 Correct 3212 ms 522732 KB Output is correct
6 Execution timed out 4067 ms 522380 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 516844 KB Output is correct
2 Correct 236 ms 516832 KB Output is correct
3 Correct 249 ms 517024 KB Output is correct
4 Correct 240 ms 516948 KB Output is correct
5 Correct 250 ms 516912 KB Output is correct
6 Correct 236 ms 516852 KB Output is correct
7 Correct 258 ms 516936 KB Output is correct
8 Correct 230 ms 516988 KB Output is correct
9 Correct 235 ms 516944 KB Output is correct
10 Correct 238 ms 516880 KB Output is correct
11 Correct 229 ms 517112 KB Output is correct
12 Correct 242 ms 516940 KB Output is correct
13 Correct 249 ms 516880 KB Output is correct
14 Correct 226 ms 516944 KB Output is correct
15 Correct 239 ms 516952 KB Output is correct
16 Correct 243 ms 516932 KB Output is correct
17 Correct 245 ms 517012 KB Output is correct
18 Correct 262 ms 516940 KB Output is correct
19 Correct 239 ms 516936 KB Output is correct
20 Correct 231 ms 516992 KB Output is correct
21 Correct 237 ms 516980 KB Output is correct
22 Correct 234 ms 516952 KB Output is correct
23 Correct 239 ms 517012 KB Output is correct
24 Correct 240 ms 516916 KB Output is correct
25 Correct 230 ms 516876 KB Output is correct
26 Correct 222 ms 516992 KB Output is correct
27 Correct 231 ms 516904 KB Output is correct
28 Correct 237 ms 516952 KB Output is correct
29 Correct 254 ms 516904 KB Output is correct
30 Correct 239 ms 516920 KB Output is correct
31 Correct 238 ms 516992 KB Output is correct
32 Correct 238 ms 516940 KB Output is correct
33 Correct 233 ms 517008 KB Output is correct
34 Correct 228 ms 516912 KB Output is correct
35 Correct 226 ms 517056 KB Output is correct
36 Correct 224 ms 516960 KB Output is correct
37 Correct 227 ms 516900 KB Output is correct
38 Correct 229 ms 517112 KB Output is correct
39 Correct 230 ms 516948 KB Output is correct
40 Correct 231 ms 516924 KB Output is correct
41 Correct 312 ms 519440 KB Output is correct
42 Correct 315 ms 519624 KB Output is correct
43 Correct 324 ms 519752 KB Output is correct
44 Correct 296 ms 519048 KB Output is correct
45 Correct 342 ms 519684 KB Output is correct
46 Correct 328 ms 519716 KB Output is correct
47 Correct 306 ms 519244 KB Output is correct
48 Correct 327 ms 519712 KB Output is correct
49 Correct 333 ms 519672 KB Output is correct
50 Correct 334 ms 519692 KB Output is correct
51 Correct 332 ms 519704 KB Output is correct
52 Correct 303 ms 519224 KB Output is correct
53 Correct 327 ms 519692 KB Output is correct
54 Correct 315 ms 519676 KB Output is correct
55 Correct 315 ms 519780 KB Output is correct
56 Correct 316 ms 519680 KB Output is correct
57 Correct 326 ms 519756 KB Output is correct
58 Correct 326 ms 519700 KB Output is correct
59 Correct 337 ms 519704 KB Output is correct
60 Correct 315 ms 519684 KB Output is correct
61 Correct 232 ms 517008 KB Output is correct
62 Correct 2142 ms 520172 KB Output is correct
63 Correct 2616 ms 521688 KB Output is correct
64 Correct 2721 ms 521596 KB Output is correct
65 Correct 2122 ms 522576 KB Output is correct
66 Correct 2741 ms 521736 KB Output is correct
67 Correct 2763 ms 521808 KB Output is correct
68 Correct 2743 ms 521576 KB Output is correct
69 Correct 2782 ms 521800 KB Output is correct
70 Correct 2662 ms 521240 KB Output is correct
71 Correct 2822 ms 521964 KB Output is correct
72 Correct 2765 ms 521892 KB Output is correct
73 Correct 2766 ms 521844 KB Output is correct
74 Correct 2823 ms 521188 KB Output is correct
75 Correct 2746 ms 520276 KB Output is correct
76 Correct 2782 ms 523012 KB Output is correct
77 Correct 1162 ms 523932 KB Output is correct
78 Correct 2677 ms 523580 KB Output is correct
79 Correct 240 ms 516856 KB Output is correct
80 Correct 213 ms 516928 KB Output is correct
81 Correct 3104 ms 519964 KB Output is correct
82 Correct 3883 ms 522640 KB Output is correct
83 Correct 3212 ms 522732 KB Output is correct
84 Execution timed out 4067 ms 522380 KB Time limit exceeded
85 Halted 0 ms 0 KB -