제출 #1184868

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184868		gyg	Tortoise (CEOI21_tortoise)	C++20	8 / 100	1 ms	328 KiB

tortoise

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array 
#define pii pair<int, int>
#define fir first 
#define sec second 
#define vec vector
const int N = 5e5 + 5, INF = 1e18;

int n;
arr<int, N> a;

arr<int, N> lf, rg;
int cst(int i, int j) { 
    assert(i <= j); // for some reason i > j
    int x = (lf[i] == -1) ? INF : 2 * (i - lf[i]);
    int y = (rg[i] == -1 || rg[i] > j) ? INF : 0;
    int z = (rg[j] == -1) ? INF : 2 * (rg[j] - j);
    return min({x, y, z}); 
}
void prp_cmp() {
    lf[0] = -1;
    for (int i = 1; i <= n; i++) {
        if (a[i] == -1) lf[i] = i;
        else lf[i] = lf[i - 1];
    }

    rg[n + 1] = -1;
    for (int i = n; i >= 1; i--) {
        if (a[i] == -1) rg[i] = i;
        else rg[i] = rg[i + 1];
    }
}

void ans_cmp() {
    set<pii> tkn;
    set<vec<int>> ord;
    int sm = 0;

    for (int i = 1; i <= n; i++) {
        if (a[i] == -1) continue;
        for (int j = 1; j <= a[i]; j++) {
            int c = (tkn.empty()) ? 0 : cst(tkn.rbegin()->fir, i);

            if (sm + c <= i) {
                tkn.insert({i, j}), ord.insert({c, i, j}), sm += c;
            } else if (ord.size()) {
                vec<int> w = *ord.rbegin();
                pii x = {w[1], w[2]};
                auto it = tkn.find(x);
                pii y = (it == tkn.begin()) ? pii{-1, -1} : *next(it, -1);
                pii z = (next(it, 1) == tkn.end()) ? pii{-1, -1} : *next(it, 1);

                int d = (y.fir == -1) ? 0 : cst(y.fir, x.fir);
                int e = (z.fir == -1) ? 0 : cst(x.fir, z.fir);
                int f = (y.fir == -1 || z.fir == -1) ? 0 : cst(y.fir, z.fir);
                
                if (w[0] <= c) break;
                // if (f + c - d - e >= 0) break; 
                tkn.erase(x);
                if (d) ord.erase({d, x.fir, x.sec});
                if (e) ord.erase({e, z.fir, z.sec});
                if (f) ord.insert({f, z.fir, z.sec});
                sm += f + c - d - e;
                
                tkn.insert({i, j}), ord.insert({c, i, j}), sm += c;
            } else break;
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (a[i] != -1) ans += a[i];
    ans -= tkn.size();
    cout << ans << '\n';
}

signed main() {
    // freopen("in", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    prp_cmp();
    ans_cmp();
} 

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