Submission #894439

#	Time	Username	Problem	Language	Result	Execution time	Memory
894439		vjudge1	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	146 ms	21076 KiB

prison

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

struct segTree{
    vector<int> v;
    int sz;
    void init(int n){
        sz = 1;
        while(sz < n) sz *= 2;
        v.assign(2 * sz, -1);
    }
    void set(int i, int val, int x, int lx, int rx){
        if(rx - lx == 1){
            v[x] = val;
            return;
        }
        int m = (lx + rx) / 2;
        if(i < m) set(i, val, 2 * x + 1, lx, m);
        else set(i, val, 2 * x + 2, m, rx);
        v[x] = max(v[2 * x + 1], v[2 * x + 2]);
    }
    void set(int i, int val){
        set(i, val, 0, 0, sz);
    }
    int calc(int l, int r, int x, int lx, int rx){
        if(lx >= l && rx <= r){
            return v[x];
        }else if(lx >= r || rx <= l) return -1;
        int m = (lx + rx) / 2;
        int c1 = calc(l, r, 2 * x + 1, lx, m);
        int c2 = calc(l, r, 2 * x + 2, m, rx);
        return max(c1, c2);
    }
    int calc(int l, int r){
        return calc(l, r, 0, 0, sz);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, D, T; cin >> n >> D >> T;
    vector<int> t(n);
    for(auto &i : t) cin >> i;
    vector<pair<int, int>> all;
    vector<int> val(n);
    for(int i = 0; i < n; i++){
        if(t[i] > T) all.push_back({T - i, i});
        else all.push_back({t[i] - i, i});
    }
    sort(all.begin(), all.end());
    int cntId = 0;
    for(int i = 0; i < n; i++){
        if(i > 0 && all[i].first != all[i-1].first) cntId++;
        val[all[i].second] = cntId;
    }
    cntId++;
    segTree st; st.init(cntId);
    vector<pair<int, int>> inv;
    int ans = n;
    for(int i = 0; i < n; i++){
        if(t[i] > T){
            int mx = st.calc(0, val[i] + 1);
            if(mx != -1){
                inv.push_back({i, mx});
            }else ans--;
        }else st.set(val[i], i);
    }
    sort(inv.begin(), inv.end());
    int curr = 0;
    vector<int> cc;
    int lst = -1;
    for(pair<int, int> p : inv){
        if(p.second <= lst) curr++;
        else{
            cc.push_back(curr);
            curr = 1;
        }
        lst = p.first;
    }
    cc.push_back(curr);
    sort(cc.begin(), cc.end());
    for(int i = (int)cc.size() - 1; i >= 0 && D > 0; i--){
        D--;
        ans -= cc[i];
    }
    cout << ans << "\n";
}

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