Submission #971067

#	Time	Username	Problem	Language	Result	Execution time	Memory
971067		vladilius	The short shank; Redemption (BOI21_prison)	C++17	80 / 100	2029 ms	481804 KiB

prison

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = double;
using pll = pair<ld, int>;
using pii = pair<int, int>;
#define f first
#define s second
const int inf = 1e9;
 
struct ST{
    vector<ld> 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, ld& 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, ld 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 {inf, 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){
        return get(1, 1, n, l, r);
    }
};

struct ST1{
    vector<int> t;
    vector<bool> p;
    int n;
    ST1(int ns){
        n = ns;
        t.resize(4 * n + 1);
        p.resize(4 * n + 1);
    }
    void push(int& v, int& vv, int& tl, int& tm, int& tr){
        if (!p[v]) return;
        p[vv] = p[vv + 1] = 1;
        t[vv] = (tm - tl + 1);
        t[vv + 1] = (tr - tm);
        p[v] = 0;
    }
    void set(int v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            t[v] = (tr - tl + 1);
            p[v] = 1;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        push(v, vv, tl, tm, tr);
        set(vv, tl, tm, l, r);
        set(vv + 1, tm + 1, tr, l, r);
        t[v] = t[vv] + t[vv + 1];
    }
    void set(int l, int r){
        set(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;
    }
    
    if (d == 1){
        int out = n;
        vector<int> hs(n + 1);
        ST1 T(n);
        for (int i = n; i > 1; i--){
            if (a[i] <= t){
                int m = t - a[i];
                T.set(i, min(n, i + m));
            }
            hs[i] = T.t[1];
        }
        for (int i = 1; i < n; i++){
            out = min(out, h[i] + hs[i + 1]);
        }
        cout<<out<<"\n";
        return 0;
    }
    
    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 = [&](ld 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];
    };
    
    ld lb = 0, rb = n;
    int tt = 40;
    while (tt--){
        ld m = (lb + rb) / 2;
        auto [v, k] = solve(m);
        if (k > d){
            lb = m;
        }
        else {
            rb = m;
        }
    }
    
    auto [v, k] = solve(lb);
    cout<<round(v - lb * d)<<"\n";
}

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 25 / 25
• Subtask 6: 0 / 20