Submission #1056904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056904		Piokemon	The short shank; Redemption (BOI21_prison)	C++17	55 / 100	961 ms	524288 KiB

prison

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

constexpr int N = 5e5;
int a[N+9];
int pref[N+9];
int suf[N+9];
int skad[N+9];
vector<ll> tree[N+9];
vector<ll> lazy[N+9];
vector<ll> dp[N+9];
int base=1;

void daj(int x, int p){
    tree[p][2*x]+=lazy[p][x]; tree[p][2*x+1]+=lazy[p][x];
    lazy[p][2*x]+=lazy[p][x]; lazy[p][2*x+1]+=lazy[p][x];
    lazy[p][x]=0;
}

void add(int x, int l, int a, int b, int p, int k, ll val){
    if (a>k || b<p)return;
    if (p<=a && b<=k){
        tree[l][x]+=val;
        lazy[l][x]+=val;
        return;
    }
    daj(x,l);
    int mid=(a+b)/2;
    add(2*x,l,a,mid,p,k,val);
    add(2*x+1,l,mid+1,b,p,k,val);
    tree[l][x]=min(tree[l][2*x],tree[l][2*x+1]);
}

int query(int x, int l, int a, int b, int p, int k){
    if (a>k || b<p)return 1e9;
    if (p<=a && b<=k)return tree[l][x];
    daj(x,l);
    int mid=(a+b)/2;
    return min(query(2*x,l,a,mid,p,k),query(2*x+1,l,mid+1,b,p,k));
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,d,t;
    cin >> n >> d >> t;
    while(base<n)base*=2;
    vector<ll> empt(4*base+9,1e9);
    vector<ll> empt2(n+3,1e9);
    vector<ll> empt3(4*base+9,0);
    for (int x=0;x<=d+1;x++){tree[x]=empt;dp[x]=empt2;lazy[x]=empt3;}
    for (int x=1;x<=n;x++){
        cin >> a[x];
    }
    vector<pair<int,int>> stos;
    stos.push_back({2e9,-1});
    for (int x=1;x<=n;x++){
        int rang=-1;
        if (a[x]<=t)rang=x+t-a[x];
        stos.push_back({rang,x});
        while(stos.back().first<x)stos.pop_back();
        skad[x]=stos.back().second;
    }
    //for (int x=1;x<=n;x++) cout << skad[x] << ' ';
    //cout << '\n';
    add(1,0,0,base-1,0,0,-1e9);
    for (int x=1;x<=n+1;x++){
        for (int y=1;y<=d+1;y++){
            dp[y][x]=query(1,y-1,0,base-1,0,x-1);
            add(1,y,0,base-1,x,x,dp[y][x]-1e9);
        }
        if (skad[x]!=-1){
            for (int y=0;y<=d+1;y++)add(1,y,0,base-1,0,skad[x],1);
        }
        /*for (int x=0;x<=n;x++) cout << query(1,0,0,base-1,x,x) << ' ';
        cout << '\n';
        for (int x=0;x<=n;x++) cout << query(1,1,0,base-1,x,x) << ' ';
        cout << '\n';
        for (int x=0;x<=n;x++) cout << query(1,2,0,base-1,x,x) << ' ';
        cout << '\n';
        cout << '\n';*/
    }
    //cout << dp[1][2] << '\n';
    //cout << dp[2][4] << '\n';
    cout << dp[d+1][n+1] << '\n';
    return 0;
}

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