제출 #1288482

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288482		esomer	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	1472 ms	117652 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);
    }
};

struct segTree2{
    vector<pair<int, int>> v;
    int sz;
    void build(int x, int lx, int rx){
        if(rx - lx == 1){
            v[x] = {0, lx};
            return;
        }
        int m = (lx + rx) / 2;
        build(2 * x + 1, lx, m);
        build(2 * x + 2, m, rx);
        v[x] = max(v[2 * x + 1], v[2 * x + 2]);
    }
    void init(int n){
        sz = 1;
        while(sz < n) sz *= 2;
        v.resize(2 * sz);
        build(0, 0, sz);
    }
    void set(int i, int val, int x, int lx, int rx){
        if(rx - lx == 1){
            v[x] = {val, lx};
            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);
    }
    pair<int, 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, -1};
        int m = (lx + rx) / 2;
        pair<int, int> c1 = calc(l, r, 2 * x + 1, lx, m);
        pair<int, int> c2 = calc(l, r, 2 * x + 2, m, rx);
        return max(c1, c2);
    }
    pair<int, int> calc(int l, int r){
        return calc(l, r, 0, 0, sz);
    }
};

bool cmp(pair<int, int> a, pair<int, int> b){
    return a.second - a.first < b.second - b.first;
}

int solve(int n, int D, int T, vector<int> t){
    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({mx, i});
            }else ans--;
        }else st.set(val[i], i);
    }
    sort(inv.begin(), inv.end(), cmp);
    segTree2 seg; seg.init(n);
    for(pair<int, int> p : inv){
        pair<int, int> mx = seg.calc(p.first, p.second + 1);
        seg.set(mx.second, 0);
        seg.set(p.second, mx.first + 1);
    }
    vector<int> cc;
    for(int i = 0; i < n; i++){
        cc.push_back(seg.calc(i, i + 1).first);
    }
    sort(cc.begin(), cc.end());
    for(int i = (int)cc.size() - 1; i >= 0 && D > 0; i--){
        D--;
        ans -= cc[i];
    }
    return ans;
}

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;
    cout << solve(n, D, T, t) << "\n";
    return 0;
}

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