oj.uz

Submission #747546

# Submission time Handle Problem Language Result Execution time Memory
747546 2023-05-24T10:02:16 Z baluteshih Mizuyokan 2 (JOI23_mizuyokan2) C++14
0 / 100
 4000 ms 520196 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
0 / 6.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 516852 KB Output is correct
2 Correct 3297 ms 519636 KB Output is correct
3 Execution timed out 4053 ms 520196 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

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

Subtask #6
0 / 11.0

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