oj.uz

Submission #747548

# Submission time Handle Problem Language Result Execution time Memory
747548 2023-05-24T10:03:57 Z baluteshih Mizuyokan 2 (JOI23_mizuyokan2) C++17
32 / 100
 3991 ms 523936 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;

        /*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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 516952 KB Output is correct
2 Incorrect 224 ms 516936 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 516952 KB Output is correct
2 Incorrect 224 ms 516936 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 516952 KB Output is correct
2 Incorrect 224 ms 516936 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 516936 KB Output is correct
2 Correct 2417 ms 520412 KB Output is correct
3 Correct 2983 ms 520612 KB Output is correct
4 Correct 3138 ms 520972 KB Output is correct
5 Correct 2656 ms 522044 KB Output is correct
6 Correct 3294 ms 523068 KB Output is correct
7 Correct 3991 ms 523000 KB Output is correct
8 Correct 3140 ms 522872 KB Output is correct
9 Correct 3932 ms 522776 KB Output is correct
10 Correct 3346 ms 522532 KB Output is correct
11 Correct 3172 ms 523936 KB Output is correct
12 Correct 3159 ms 522788 KB Output is correct
13 Correct 3075 ms 522800 KB Output is correct
14 Correct 3042 ms 522920 KB Output is correct
15 Correct 3094 ms 522704 KB Output is correct
16 Correct 3071 ms 522880 KB Output is correct
17 Correct 1528 ms 523912 KB Output is correct
18 Correct 2982 ms 523636 KB Output is correct

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 516944 KB Output is correct
2 Incorrect 227 ms 516864 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 516952 KB Output is correct
2 Incorrect 224 ms 516936 KB Output isn't correct
3 Halted 0 ms 0 KB -