Submission #894604

#	Time	Username	Problem	Language	Result	Execution time	Memory
894604		esomer	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	1530 ms	136604 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 fast(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 slow(int n, int D, int T, vector<int> t){
    int realAns = n;
    for(int i = 0; i < n; i++){
        int ans = 0;
        int mn = 2e9;
        for(int j = 0; j <= i; j++){
            mn++;
            mn = min(mn, t[j]);
            if(mn <= T) ans++;
            // cout << "j " << j << " mn " << mn << " ans " << ans << "\n";
        }
        mn = 2e9;
        for(int j = i+1; j < n; j++){
            mn++;
            mn = min(mn, t[j]);
            if(mn <= T) ans++;
            // cout << "j " << j << " mn " << mn << " ans " << ans << "\n";
        }
        // cout << "i " << i << " ans " << ans << "\n";
        realAns = min(realAns, ans);
    }
    return realAns;
}

mt19937 gen(time(0));

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

    string s; 
    // cin >> s; 
    s = "RUN";
    if(s == "RUN"){
        int n, D, T; cin >> n >> D >> T;
        vector<int> t(n);
        for(auto &i : t) cin >> i;
        cout << fast(n, D, T, t) << "\n";
        // cout << "Fast" << endl << fast(n, D, T, t) << "\n";
        // cout << "Slow" << endl << slow(n, D, T, t) << "\n";
        return 0;
    }

    for(int tt = 0; tt < 1000; tt++){
        int n = gen() % 100 + 1;
        int D = 1;
        int T = gen() % 10000 + 1;
        vector<int> t(n);
        for(int i = 0; i < n; i++) t[i] = gen() % 1100000 + 1;
        int ans1 = fast(n, D, T, t);
        int ans2 = slow(n, D, T, t);
        if(ans1 != ans2){
            cout << n << " " << D << " " << T << "\n";
            for(int x : t) cout << x << " "; 
            cout << "\n";
            cout << "Ans1: " << ans1 << "\n";
            cout << "Ans2: " << ans2 << "\n";
            return 0;
        }
    }
    cout << "Nothing\n";
}

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