oj.uz

Submission #747561

# Submission time Handle Problem Language Result Execution time Memory
747561 2023-05-24T10:22:28 Z baluteshih Mizuyokan 2 (JOI23_mizuyokan2) C++14
100 / 100
 1996 ms 524048 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);
        }

        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;
            }
        }

        pii one = pll(a - 1, -1);
        pii two = pll(a, 0);
        int rgt = min(b - 1, a + C);
        for (int j = a + 1; j <= rgt; ++j) {
            if (lft[j] - 1 > one.X) one.X = j, one.Y += 2;
            if (lft[j] - 1 > two.X) two.X = j, two.Y += 2;
        }

        if (rgt + 1 <= b - 1) {
            Node res = query(rgt + 1, b - 1, 1);
            if (one.X < rgt + 1 - C - 1) one = one + res.mx[C];
            else one = one + res.mx[rgt + 1 - one.X - 1];
            if (two.X < rgt + 1 - C - 1) two = two + res.mx[C];
            else two = two + res.mx[rgt + 1 - two.X - 1];
        }

        int ans = max(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];

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 516860 KB Output is correct
2 Correct 224 ms 516920 KB Output is correct
3 Correct 332 ms 517056 KB Output is correct
4 Correct 224 ms 516872 KB Output is correct
5 Correct 230 ms 516868 KB Output is correct
6 Correct 268 ms 516880 KB Output is correct
7 Correct 253 ms 516880 KB Output is correct
8 Correct 232 ms 516852 KB Output is correct
9 Correct 264 ms 516952 KB Output is correct
10 Correct 234 ms 516924 KB Output is correct
11 Correct 238 ms 516940 KB Output is correct
12 Correct 269 ms 517056 KB Output is correct
13 Correct 258 ms 516916 KB Output is correct
14 Correct 244 ms 516864 KB Output is correct
15 Correct 270 ms 516948 KB Output is correct
16 Correct 232 ms 516940 KB Output is correct
17 Correct 226 ms 516920 KB Output is correct
18 Correct 227 ms 516972 KB Output is correct
19 Correct 236 ms 516940 KB Output is correct
20 Correct 233 ms 516892 KB Output is correct
21 Correct 233 ms 516908 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 516860 KB Output is correct
2 Correct 224 ms 516920 KB Output is correct
3 Correct 332 ms 517056 KB Output is correct
4 Correct 224 ms 516872 KB Output is correct
5 Correct 230 ms 516868 KB Output is correct
6 Correct 268 ms 516880 KB Output is correct
7 Correct 253 ms 516880 KB Output is correct
8 Correct 232 ms 516852 KB Output is correct
9 Correct 264 ms 516952 KB Output is correct
10 Correct 234 ms 516924 KB Output is correct
11 Correct 238 ms 516940 KB Output is correct
12 Correct 269 ms 517056 KB Output is correct
13 Correct 258 ms 516916 KB Output is correct
14 Correct 244 ms 516864 KB Output is correct
15 Correct 270 ms 516948 KB Output is correct
16 Correct 232 ms 516940 KB Output is correct
17 Correct 226 ms 516920 KB Output is correct
18 Correct 227 ms 516972 KB Output is correct
19 Correct 236 ms 516940 KB Output is correct
20 Correct 233 ms 516892 KB Output is correct
21 Correct 233 ms 516908 KB Output is correct
22 Correct 233 ms 516880 KB Output is correct
23 Correct 237 ms 516904 KB Output is correct
24 Correct 268 ms 516964 KB Output is correct
25 Correct 232 ms 516940 KB Output is correct
26 Correct 271 ms 516940 KB Output is correct
27 Correct 224 ms 516972 KB Output is correct
28 Correct 253 ms 516956 KB Output is correct
29 Correct 260 ms 516952 KB Output is correct
30 Correct 244 ms 516984 KB Output is correct
31 Correct 247 ms 517000 KB Output is correct
32 Correct 235 ms 517004 KB Output is correct
33 Correct 253 ms 516964 KB Output is correct
34 Correct 231 ms 516880 KB Output is correct
35 Correct 238 ms 516992 KB Output is correct
36 Correct 253 ms 517096 KB Output is correct
37 Correct 251 ms 516984 KB Output is correct
38 Correct 247 ms 516884 KB Output is correct
39 Correct 256 ms 516944 KB Output is correct
40 Correct 238 ms 516904 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 516860 KB Output is correct
2 Correct 224 ms 516920 KB Output is correct
3 Correct 332 ms 517056 KB Output is correct
4 Correct 224 ms 516872 KB Output is correct
5 Correct 230 ms 516868 KB Output is correct
6 Correct 268 ms 516880 KB Output is correct
7 Correct 253 ms 516880 KB Output is correct
8 Correct 232 ms 516852 KB Output is correct
9 Correct 264 ms 516952 KB Output is correct
10 Correct 234 ms 516924 KB Output is correct
11 Correct 238 ms 516940 KB Output is correct
12 Correct 269 ms 517056 KB Output is correct
13 Correct 258 ms 516916 KB Output is correct
14 Correct 244 ms 516864 KB Output is correct
15 Correct 270 ms 516948 KB Output is correct
16 Correct 232 ms 516940 KB Output is correct
17 Correct 226 ms 516920 KB Output is correct
18 Correct 227 ms 516972 KB Output is correct
19 Correct 236 ms 516940 KB Output is correct
20 Correct 233 ms 516892 KB Output is correct
21 Correct 233 ms 516908 KB Output is correct
22 Correct 233 ms 516880 KB Output is correct
23 Correct 237 ms 516904 KB Output is correct
24 Correct 268 ms 516964 KB Output is correct
25 Correct 232 ms 516940 KB Output is correct
26 Correct 271 ms 516940 KB Output is correct
27 Correct 224 ms 516972 KB Output is correct
28 Correct 253 ms 516956 KB Output is correct
29 Correct 260 ms 516952 KB Output is correct
30 Correct 244 ms 516984 KB Output is correct
31 Correct 247 ms 517000 KB Output is correct
32 Correct 235 ms 517004 KB Output is correct
33 Correct 253 ms 516964 KB Output is correct
34 Correct 231 ms 516880 KB Output is correct
35 Correct 238 ms 516992 KB Output is correct
36 Correct 253 ms 517096 KB Output is correct
37 Correct 251 ms 516984 KB Output is correct
38 Correct 247 ms 516884 KB Output is correct
39 Correct 256 ms 516944 KB Output is correct
40 Correct 238 ms 516904 KB Output is correct
41 Correct 350 ms 520700 KB Output is correct
42 Correct 337 ms 521012 KB Output is correct
43 Correct 357 ms 520920 KB Output is correct
44 Correct 394 ms 519884 KB Output is correct
45 Correct 335 ms 521232 KB Output is correct
46 Correct 409 ms 520348 KB Output is correct
47 Correct 326 ms 519868 KB Output is correct
48 Correct 339 ms 520636 KB Output is correct
49 Correct 342 ms 520376 KB Output is correct
50 Correct 345 ms 520484 KB Output is correct
51 Correct 339 ms 520332 KB Output is correct
52 Correct 345 ms 520360 KB Output is correct
53 Correct 335 ms 521280 KB Output is correct
54 Correct 334 ms 520288 KB Output is correct
55 Correct 329 ms 520252 KB Output is correct
56 Correct 359 ms 520240 KB Output is correct
57 Correct 347 ms 520256 KB Output is correct
58 Correct 374 ms 520268 KB Output is correct
59 Correct 329 ms 521300 KB Output is correct
60 Correct 332 ms 521304 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 516928 KB Output is correct
2 Correct 384 ms 521360 KB Output is correct
3 Correct 497 ms 520680 KB Output is correct
4 Correct 555 ms 520412 KB Output is correct
5 Correct 464 ms 520648 KB Output is correct
6 Correct 637 ms 520916 KB Output is correct
7 Correct 692 ms 520820 KB Output is correct
8 Correct 643 ms 520704 KB Output is correct
9 Correct 616 ms 520904 KB Output is correct
10 Correct 591 ms 520040 KB Output is correct
11 Correct 650 ms 520920 KB Output is correct
12 Correct 662 ms 520816 KB Output is correct
13 Correct 656 ms 520764 KB Output is correct
14 Correct 683 ms 520224 KB Output is correct
15 Correct 633 ms 520144 KB Output is correct
16 Correct 705 ms 520060 KB Output is correct
17 Correct 432 ms 519928 KB Output is correct
18 Correct 660 ms 519792 KB Output is correct

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 516916 KB Output is correct
2 Correct 237 ms 516892 KB Output is correct
3 Correct 1512 ms 519988 KB Output is correct
4 Correct 1742 ms 520240 KB Output is correct
5 Correct 1567 ms 522424 KB Output is correct
6 Correct 1899 ms 522452 KB Output is correct
7 Correct 1871 ms 522588 KB Output is correct
8 Correct 1847 ms 522592 KB Output is correct
9 Correct 1880 ms 522344 KB Output is correct
10 Correct 1896 ms 522928 KB Output is correct
11 Correct 1887 ms 522308 KB Output is correct
12 Correct 1835 ms 522280 KB Output is correct
13 Correct 1851 ms 522440 KB Output is correct
14 Correct 1866 ms 522164 KB Output is correct
15 Correct 1863 ms 522276 KB Output is correct
16 Correct 1020 ms 522760 KB Output is correct
17 Correct 1265 ms 522480 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 516860 KB Output is correct
2 Correct 224 ms 516920 KB Output is correct
3 Correct 332 ms 517056 KB Output is correct
4 Correct 224 ms 516872 KB Output is correct
5 Correct 230 ms 516868 KB Output is correct
6 Correct 268 ms 516880 KB Output is correct
7 Correct 253 ms 516880 KB Output is correct
8 Correct 232 ms 516852 KB Output is correct
9 Correct 264 ms 516952 KB Output is correct
10 Correct 234 ms 516924 KB Output is correct
11 Correct 238 ms 516940 KB Output is correct
12 Correct 269 ms 517056 KB Output is correct
13 Correct 258 ms 516916 KB Output is correct
14 Correct 244 ms 516864 KB Output is correct
15 Correct 270 ms 516948 KB Output is correct
16 Correct 232 ms 516940 KB Output is correct
17 Correct 226 ms 516920 KB Output is correct
18 Correct 227 ms 516972 KB Output is correct
19 Correct 236 ms 516940 KB Output is correct
20 Correct 233 ms 516892 KB Output is correct
21 Correct 233 ms 516908 KB Output is correct
22 Correct 233 ms 516880 KB Output is correct
23 Correct 237 ms 516904 KB Output is correct
24 Correct 268 ms 516964 KB Output is correct
25 Correct 232 ms 516940 KB Output is correct
26 Correct 271 ms 516940 KB Output is correct
27 Correct 224 ms 516972 KB Output is correct
28 Correct 253 ms 516956 KB Output is correct
29 Correct 260 ms 516952 KB Output is correct
30 Correct 244 ms 516984 KB Output is correct
31 Correct 247 ms 517000 KB Output is correct
32 Correct 235 ms 517004 KB Output is correct
33 Correct 253 ms 516964 KB Output is correct
34 Correct 231 ms 516880 KB Output is correct
35 Correct 238 ms 516992 KB Output is correct
36 Correct 253 ms 517096 KB Output is correct
37 Correct 251 ms 516984 KB Output is correct
38 Correct 247 ms 516884 KB Output is correct
39 Correct 256 ms 516944 KB Output is correct
40 Correct 238 ms 516904 KB Output is correct
41 Correct 350 ms 520700 KB Output is correct
42 Correct 337 ms 521012 KB Output is correct
43 Correct 357 ms 520920 KB Output is correct
44 Correct 394 ms 519884 KB Output is correct
45 Correct 335 ms 521232 KB Output is correct
46 Correct 409 ms 520348 KB Output is correct
47 Correct 326 ms 519868 KB Output is correct
48 Correct 339 ms 520636 KB Output is correct
49 Correct 342 ms 520376 KB Output is correct
50 Correct 345 ms 520484 KB Output is correct
51 Correct 339 ms 520332 KB Output is correct
52 Correct 345 ms 520360 KB Output is correct
53 Correct 335 ms 521280 KB Output is correct
54 Correct 334 ms 520288 KB Output is correct
55 Correct 329 ms 520252 KB Output is correct
56 Correct 359 ms 520240 KB Output is correct
57 Correct 347 ms 520256 KB Output is correct
58 Correct 374 ms 520268 KB Output is correct
59 Correct 329 ms 521300 KB Output is correct
60 Correct 332 ms 521304 KB Output is correct
61 Correct 241 ms 516928 KB Output is correct
62 Correct 384 ms 521360 KB Output is correct
63 Correct 497 ms 520680 KB Output is correct
64 Correct 555 ms 520412 KB Output is correct
65 Correct 464 ms 520648 KB Output is correct
66 Correct 637 ms 520916 KB Output is correct
67 Correct 692 ms 520820 KB Output is correct
68 Correct 643 ms 520704 KB Output is correct
69 Correct 616 ms 520904 KB Output is correct
70 Correct 591 ms 520040 KB Output is correct
71 Correct 650 ms 520920 KB Output is correct
72 Correct 662 ms 520816 KB Output is correct
73 Correct 656 ms 520764 KB Output is correct
74 Correct 683 ms 520224 KB Output is correct
75 Correct 633 ms 520144 KB Output is correct
76 Correct 705 ms 520060 KB Output is correct
77 Correct 432 ms 519928 KB Output is correct
78 Correct 660 ms 519792 KB Output is correct
79 Correct 243 ms 516916 KB Output is correct
80 Correct 237 ms 516892 KB Output is correct
81 Correct 1512 ms 519988 KB Output is correct
82 Correct 1742 ms 520240 KB Output is correct
83 Correct 1567 ms 522424 KB Output is correct
84 Correct 1899 ms 522452 KB Output is correct
85 Correct 1871 ms 522588 KB Output is correct
86 Correct 1847 ms 522592 KB Output is correct
87 Correct 1880 ms 522344 KB Output is correct
88 Correct 1896 ms 522928 KB Output is correct
89 Correct 1887 ms 522308 KB Output is correct
90 Correct 1835 ms 522280 KB Output is correct
91 Correct 1851 ms 522440 KB Output is correct
92 Correct 1866 ms 522164 KB Output is correct
93 Correct 1863 ms 522276 KB Output is correct
94 Correct 1020 ms 522760 KB Output is correct
95 Correct 1265 ms 522480 KB Output is correct
96 Correct 1449 ms 522088 KB Output is correct
97 Correct 1742 ms 523224 KB Output is correct
98 Correct 1600 ms 523568 KB Output is correct
99 Correct 1928 ms 523272 KB Output is correct
100 Correct 1961 ms 522988 KB Output is correct
101 Correct 1873 ms 522920 KB Output is correct
102 Correct 1881 ms 522896 KB Output is correct
103 Correct 1864 ms 524048 KB Output is correct
104 Correct 1871 ms 522988 KB Output is correct
105 Correct 1857 ms 522788 KB Output is correct
106 Correct 1962 ms 522724 KB Output is correct
107 Correct 1996 ms 522772 KB Output is correct
108 Correct 1886 ms 522768 KB Output is correct
109 Correct 1022 ms 523888 KB Output is correct
110 Correct 1213 ms 523600 KB Output is correct