Submission #868149

#	Time	Username	Problem	Language	Result	Execution time	Memory
868149		HossamHero7	The short shank; Redemption (BOI21_prison)	C++14	80 / 100	2016 ms	184212 KiB

prison

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
struct segtree{
    int n;
    vector<pair<int,int>> tree;
    vector<int> lazy;
    void build(int node,int l,int r){
        if(l == r) return tree[node] = {0,l-1} , void();
        int md = l + r >> 1;
        build(node<<1,l,md) , build(node<<1|1,md+1,r);
        tree[node] = max(tree[node<<1],tree[node<<1|1]);
    }
    segtree(int _n){
        n = _n;
        tree.resize(4*n+5);
        lazy.resize(4*n+5);
        build(1,1,n);
    }
    void prop(int node,int l,int r){
        tree[node].first += lazy[node];
        if(l != r){
            lazy[node<<1] += lazy[node];
            lazy[node<<1|1] += lazy[node];
        }
        lazy[node] = 0;
    }
    void update(int node,int l,int r,int lQ,int rQ,int val){
        if(l>r) return;
        if(lazy[node]) prop(node,l,r);
        if(lQ>r || l>rQ) return;
        if(lQ<=l&&r<=rQ){
            lazy[node] += val;
            prop(node,l,r);
            return;
        }
        int md = l + r >> 1;
        update(node<<1,l,md,lQ,rQ,val) , update(node<<1|1,md+1,r,lQ,rQ,val);
        tree[node] = max(tree[node<<1],tree[node<<1|1]);
    }
    void update(int l,int r,int val){
        update(1,1,n,l+1,r+1,val);
    }
    pair<int,int> getMaxPoint(){
        if(lazy[1]) prop(1,1,n);
        return tree[1];
    }
};
void solve(){
    int n,d,t;
    cin>>n>>d>>t;
    vector<int> a(n);
    for(auto &i:a) cin>>i;
    vector<int> lst(n);
    vector<int> sts;
    int ans = 0;
    vector<int> starts(n,-1);
    segtree sg(n);
    for(int i=0;i<n;i++){
        while(sts.size()){    
            int j = sts.back();
            int dur = t - a[j] + j;
            if(dur < i) sts.pop_back();
            else break;
        }
        if(a[i] <= t){
            ans ++;
            while(sts.size()){
                int j = sts.back();
                int dur1 = t - a[j] + j;
                int dur2 = t - a[i] + i;
                if(dur2 >= dur1) sts.pop_back();
                else break;
            }
            sts.push_back(i);
        }
        else {
            if(sts.size()){
                lst[i] = sts.back() , ans ++;
                sg.update(lst[i],i-1,1);
                starts[i-1] = lst[i];
            }
        }
    }
    set<int> ends;
    for(int i=0;i<n;i++){
        if(~starts[i]) ends.insert(i);
    }
    while(d--){
        auto [f,p] = sg.getMaxPoint();
        ans -= f;
        auto it = ends.lower_bound(p);
        while(it != ends.end()){
            int x = *it;
            int s = starts[x];
            if(s <= p) {
                sg.update(s,x,-1);
                starts[x] = -1;
            }
            if(~starts[x]) it ++;
            else {
                auto itt = it;
                itt ++;
                ends.erase(it);
                it = itt;
            }
        }
    }
    cout<<ans<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

prison.cpp: In member function 'void segtree::build(int, int, int)':
prison.cpp:11:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   11 |         int md = l + r >> 1;
      |                  ~~^~~
prison.cpp: In member function 'void segtree::update(int, int, int, int, int, int)':
prison.cpp:38:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         int md = l + r >> 1;
      |                  ~~^~~
prison.cpp: In function 'void solve()':
prison.cpp:91:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |         auto [f,p] = sg.getMaxPoint();
      |              ^

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