Submission #1057278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057278		Zbyszek99	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	719 ms	273852 KiB

prison

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define size(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
//mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

const int MAXN = 2000010;
const int wiel_tree = 1024*4096-1;

pii drzewo[wiel_tree];
int oper[wiel_tree]; 
int n,d,t;
int pre[MAXN];
int max_pre[MAXN];
vector<int> graf[MAXN];
int arr[MAXN];
int parent[MAXN];
int cur_pre = 1;
int depth[MAXN];
bool was_take[MAXN];
bool was_take2[MAXN];

void add_pom(int akt, int p1, int p2, int s1, int s2)
{
    if(akt != 1) drzewo[akt-1].ff += oper[akt/2-1];
    if(akt != 1) oper[akt-1] += oper[akt/2-1];
    if(p2 < s1 || p1 > s2) return;
    if(p1 >= s1 && p2 <= s2)
    {
        drzewo[akt-1].ff--;
        oper[akt-1]--;
        return;
    }
    add_pom(akt*2,p1,(p1+p2)/2,s1,s2);
    add_pom(akt*2+1,(p1+p2)/2+1,p2,s1,s2);
    drzewo[akt-1] = max(drzewo[akt*2-1],drzewo[akt*2]);
    oper[akt-1] = 0;
}

pii get_max()
{
    return drzewo[0];
}

void dfs(int v, int dep = 1)
{
    depth[v] = dep;
    dep++;
    pre[v] = cur_pre++;
    max_pre[v] = pre[v];
    forall(it,graf[v])
    {
        dfs(it,dep);
        max_pre[v] = max_pre[it];
    }
}

void solve()
{
    cin >> n >> d >> t;
    rep(i,n) cin >> arr[i];
    stack<int> st;
    rep(i,n) parent[i] = -1;
    for(int i = n-1; i >= 0; i--)
    {
        if(arr[i] > t && size(st) > 0)
        {
            graf[st.top()].pb(i);
            parent[i] = st.top();
        }
        st.push(i);
        while(size(st) > 0 && i + t - arr[i] >= st.top())
        {
            was_take2[st.top()] = true;
            st.pop();
        }
    }
    rep(i,n)
    {
        if(!was_take2[parent[i]]) parent[i] = -1;
    }
    rep(i,n)
    {
        //cerr << parent[i] << " " << arr[i] << " " << was_take2[i] << " info\n";
        if(parent[i] == -1 && arr[i] > t && was_take2[i])
        {
            dfs(i);
        }
    }
    rep(i,n)
    {
        //cerr << i << " " << depth[i] << " " << pre[i] << " dep\n";
        drzewo[wiel_tree/2+pre[i]] = {depth[i],i};
    }
    rep2(i,wiel_tree/2+n,wiel_tree-1) drzewo[i] = {0,0};
    for(int i = wiel_tree/2-1; i >= 0; i--)
    {
        drzewo[i] = max(drzewo[i*2+1],drzewo[i*2+2]);
    }
    int ans = n - size(st);
    rep(i,d)
    {
        pii m = get_max();
    //    cerr << ans << " " << m.ff << " " << m.ss << "\n";
        if(m.ff == 0) break;
        ans -= m.ff;
        int v = m.ss;
        while(v != -1 && !was_take[v])
        {
            was_take[v] = true;
            add_pom(1,0,wiel_tree/2,pre[v],max_pre[v]);
            v = parent[v];
        }
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random();
    int t = 1;
    //cin >> t;
    while(t--) 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