Submission #747561

#	Time	Username	Problem	Language	Result	Execution time	Memory
747561		baluteshih	Mizuyokan 2 (JOI23_mizuyokan2)	C++14	100 / 100	1996 ms	524048 KiB

mizuyokan2

#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 / 6
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 32 / 32
• Subtask 5: 29 / 29
• Subtask 6: 11 / 11