제출 #680210

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
680210		jhwest2	Tortoise (CEOI21_tortoise)	C++17	0 / 100	1 ms	340 KiB

tortoise

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 505050;

int n, a[N], d[N], yes[N];

struct seg {
    ll sum[8 * N]; int tree[8 * N], lazy[8 * N];

    void push(int l, int r, int x) {
        if (lazy[x]) {
            tree[x] = lazy[x];
            sum[x] = 1ll * (r - l + 1) * lazy[x];
            if (l != r) {
                lazy[2 * x] = lazy[x];
                lazy[2 * x + 1] = lazy[x];
            }
            lazy[x] = 0;
        }
    }
    void update(int a, int b, int v, int l, int r, int x) {
        push(l, r, x);
        if (b < l || a > r)
            return;
        if (a <= l && r <= b) {
            lazy[x] = v; push(l, r, x);
            return;
        }
        int m = (l + r) / 2;
        update(a, b, v, l, m, 2 * x);
        update(a, b, v, m + 1, r, 2 * x + 1);

        tree[x] = max(tree[2 * x], tree[2 * x + 1]);
        sum[x] = sum[2 * x] + sum[2 * x + 1];
    }
    int query(int k, int l, int r, int x) {
        push(l, r, x);
        if (l == r)
            return l;
        int m = (l + r) / 2;
        push(l, m, 2 * x);
        if (tree[2 * x] > k)
            return query(k, l, m, 2 * x);
        else
            return query(k, m + 1, r, 2 * x + 1);
    }
    ll get_sum(int a, int b, int l, int r, int x) {
        push(l, r, x);
        if (b < l || a > r)
            return 0ll;
        if (a <= l && r <= b)
            return sum[x];

        int m = (l + r) / 2;
        return get_sum(a, b, l, m, 2 * x) + get_sum(a, b, m + 1, r, 2 * x + 1);
    }
} t1;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] != -1)
            ans += a[i];
        d[i] = 1e9;
    }

    int p = -1, q = -1;
    for (int i = 1; i <= n; i++) {
        if (a[i] == -1)
            p = i;
        else {
            if (p != -1)
                d[i] = i - p;
        }
    }
    p = -1;
    for (int i = n; i >= 1; i--) {
        if (a[i] == -1)
            p = i;
        else {
            if (p != -1)
                d[i] = min(d[i], p - i);
            if (p != -1 && p < q)
                yes[i] = 1;
            if (q == -1)
                yes[i] = 2;
            q = i;
        }
    }
    
    t1.update(n, 2 * n, 1e9, 1, 2 * n, 1);
    int l = n, x = -1, offset = 0, store = 0;
    for (int i = 1; i <= n; i++) {


        if (a[i] == -1) {
            offset++;
            continue;
        }
        a[i] += store;
        store = 0;

        if (a[i] == 0)
            continue;

        a[i] -= 1;
        store = 1;

        int p = t1.query(2 * d[i], 1, 2 * n, 1);
        ll s = t1.get_sum(1, p - 1, 1, 2 * n, 1) + offset;

        if (s <= 2 * (i - 1)) {
            int r = (2 * (i - 1) - s) / (2 * d[i]);
            r = min(r, a[i] - 1);
            if (r != -1)
                t1.update(p, p + r, 2 * d[i], 1, 2 * n, 1);
        }
        if (store && yes[i] == 1) 
            store = 0, --l;
        if (yes[i] == 2) {
            x = i;
            break;
        }

        ++offset;
    }
    
    p = t1.query((int)1e9 - 1, 1, 2 * n, 1);
    if (store && offset + t1.get_sum(l, p - 1, 1, 2 * n, 1) <= 2 * (x - 1))
        --l;
        
    cout << ans - (p - l);
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 25
• Subtask 5: 0 / 27