Submission #591751

#	Time	Username	Problem	Language	Result	Execution time	Memory
591751		Lobo	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	1098 ms	417556 KiB

prison

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
 
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const int inf1 = (int) 2e9 + 10;
// #define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define MAX(a,b) a > b ? a : b
#define MIN(a,b) a < b ? a : b
 
const int maxn = 2e6+10;
 
int n, d, T, r[maxn], trT[4*maxn], lzqtd[4*maxn], pai[maxn], mark[maxn];
pair<int,int> trqtd[4*maxn], trr[4*maxn], deep[maxn];
vector<int> fq[maxn], g[maxn];
 
void buildT(int no, int l, int r) {
    trT[no] = inf1;
    if(l != r) {
        int f1=((no)<<1);
        int f2=((no)<<1)+1;
        int mid = (l+r)>>1;
        buildT(f1,l,mid);
        buildT(f2,mid+1,r);
    }
}
 
void attT(int no, int l, int r, int pos, int val) {
    if(l > pos || r < pos) return;
    if(l == r) {
        trT[no] = val;
        return;
    }
    int f1=((no)<<1);
    int f2=((no)<<1)+1;
    int mid = (l+r)>>1;
    attT(f1,l,mid,pos,val);
    attT(f2,mid+1,r,pos,val);
    trT[no] = min(trT[f1],trT[f2]);
}
 
int findT(int no, int l, int r, int val) {
    if(l == r) return l;
    int f1 = ((no)<<1);
    int f2 = ((no)<<1)+1;
    int mid = (l+r)>>1;
    if(trT[f2] <= val) return findT(f2,mid+1,r,val);
    return findT(f1,l,mid,val);
}

void dfsdeep(int u) {
    deep[u] = mp(1,u);
    for(auto v : g[u]) {
        dfsdeep(v);
        deep[u] = max(deep[u],mp(deep[v].fr+1,deep[v].sc));
    }
}

void solve() {
    cin >> n >> d >> T;
    int ans = 0;
    buildT(1,1,n);
    vector<pair<pair<int,int>,int>> segs;
    for(int i = 1; i <= n; i++) {
        int t; cin >> t;
        attT(1,1,n,i,t-i);
        if(trT[1] > T-i) {
            r[i] = n+1;
        }
        else {
            r[i] = findT(1,1,n,T-i);
            ans++;
        }
        //i aumenta o qtd de r[i] até i-1
        if(r[i] != i && r[i] != n+1) {
            segs.pb(mp(mp(r[i],i),0));
            segs.pb(mp(mp(i,i),1));
        }
        // cout << i << " " << r[i] << endl;
    }

    stack<int> st;
    int cnt = 0;
    sort(all(segs));
    for(auto X : segs) {
        if(X.sc == 0) {
            ++cnt;
            if(st.size()) {
                pai[cnt] = st.top();
                g[st.top()].pb(cnt);
            }
            st.push(cnt);
        }
        else {
            st.pop();
        }
    }

    // for(int i = 1; i <= cnt; i++) {
    //     cout << i << " " << pai[i] << endl;
    // }

    for(int i = 1; i <= cnt; i++) {
        if(pai[i] == 0) dfsdeep(i);
    }
    for(int i = 1; i <= cnt; i++) {
        fq[deep[i].fr].pb(i);
        // cout << i << " " << deep[i].sc << endl;
    }

    for(int i = n; i >= 1; i--) {
        if(d == 0) break;
        for(auto id : fq[i]) {
            if(d == 0) break;
            if(mark[id]) continue;
            d--;
            int v = deep[id].sc;
            while(v != 0 && mark[v] == 0) {
                ans--;
                mark[v] = 1;
                v = pai[v];
            }
        }
    }
    cout << ans << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

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