oj.uz

Submission #971040

# Submission time Handle Problem Language Result Execution time Memory
971040 2024-04-27T21:11:17 Z vladilius The short shank; Redemption (BOI21_prison) C++17
0 / 100
 2000 ms 116316 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, int>;
using pii = pair<int, int>;
#define f first
#define s second
const int inf = numeric_limits<int> :: max();
const ll infll = 1e18;
 
struct ST{
    vector<ll> t, p;
    vector<int> k;
    int n;
    
    void build(int v, int tl, int tr){
        if (tl == tr){
            k[v] = tl;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        build(vv, tl, tm);
        build(vv + 1, tm + 1, tr);
        t[v] = tl;
    }
    
    ST(int ns){
        n = ns;
        t.resize(4 * n);
        p.resize(4 * n);
        k.resize(4 * n);
        build(1, 1, n);
    }
    void push(int& v, int& vv){
        if (!p[v]) return;
        p[vv] += p[v]; t[vv] += p[v];
        p[vv + 1] += p[v]; t[vv + 1] += p[v];
        p[v] = 0;
    }
    void add(int v, int tl, int tr, int& l, int& r, ll& x){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            t[v] += x;
            p[v] += x;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        push(v, vv);
        add(vv, tl, tm, l, r, x);
        add(vv + 1, tm + 1, tr, l, r, x);
        if (t[vv] > t[vv + 1]){
            t[v] = t[vv + 1];
            k[v] = k[vv + 1];
        }
        else {
            t[v] = t[vv];
            k[v] = k[vv];
        }
        t[v] = min(t[vv], t[vv + 1]);
    }
    void add(int l, int r, ll x){
        if (l > r) return;
        add(1, 1, n, l, r, x);
    }
    pll get(int v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return {infll, 0};
        if (l <= tl && tr <= r){
            return {t[v], k[v]};
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        push(v, vv);
        return min(get(vv, tl, tm, l, r), get(vv + 1, tm + 1, tr, l, r));
    }
    pll get(int l, int r){
        if (l > r) return {inf, 0};
        return get(1, 1, n, l, r);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, d, t; cin>>n>>d>>t;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>a[i];
    }
    
    vector<int> h(n + 1);
    int mx = 0, cnt = 0;
    for (int j = 1; j <= n; j++){
        if (a[j] <= t){
            int m = t - a[j];
            mx = max(mx, j + m);
        }
        cnt += (j <= mx);
        h[j] = cnt;
    }
    
    vector<int> r(n + 1);
    for (int i = 1; i <= n; i++){
        if (a[i] > t) continue;
        int m = t - a[i];
        r[i] = i + m;
    }
    
    const int lg = ceil(log2(n));
    vector<vector<int>> sp(n + 1, vector<int>(lg));
    for (int i = 1; i <= n; i++){
        sp[i][0] = r[i];
    }
    for (int j = 1; j < lg; j++){
        for (int i = 1; i + (1 << j) <= n + 1; i++){
            sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
        }
    }
    vector<int> log(n + 1);
    for (int i = 2; i <= n; i++){
        log[i] = log[i / 2] + 1;
    }
    
    auto check = [&](int x, int y){
        int k = log[y - x + 1];
        return max(sp[x][k], sp[y - (1 << k) + 1][k]) >= y;
    };

    vector<int> f(n);
    for (int i = 1; i < n; i++){
        auto good = [&](int m){
            return check(m, i + 1);
        };
        int l = 0, r = i + 1;
        while (l + 1 < r){
            int m = (l + r) / 2;
            if (good(m)){
                l = m;
            }
            else {
                r = m - 1;
            }
        }
        if (good(r)) l = r;
        f[i] = l;
    }
    
    auto solve = [&](int m){
        pll dp[n + 1];
        ST T(n);
        for (int i = 1; i <= n; i++){
            dp[i] = {h[i], 0};
            T.add(1, f[i - 1] - 1, 1);
            auto [v, j] = T.get(1, i - 1);
            dp[i] = min(dp[i], {v + m, dp[j].s + 1});
            T.add(i, i, dp[i].f);
        }
        return dp[n];
    };
    
    int lb = 0, rb = n;
    while (lb + 1 < rb){
        int m = (lb + rb) / 2;
        auto [v, k] = solve(m);
        if (k > d){
            lb = m + 1;
        }
        else {
            rb = m;
        }
    }
    
    auto [v, k] = solve(lb);
    cout<<v - lb * d<<"\n";
}

Subtask #1
0 / 15.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 2079 ms 116316 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 628 ms 16692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

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

Subtask #6
0 / 20.0

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