Submission #1205098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205098		lighton	Tortoise (CEOI21_tortoise)	C++20	100 / 100	864 ms	87000 KiB

tortoise

#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e18;
int N;
ll sum,ans;
ll arr[1000001];
ll lc[1000001], rc[1000001];
ll grp[1000001], grpsum[1000001] , grpnow;
set<array<ll,3> > pq;
set<ll> bar;
set<ll> S, nS;

struct Seg{
    ll arr[4000001];
    ll lazy[4000001];
    void propagate(int now, int s, int e){
        arr[now] += lazy[now];
        if(s!=e){ lazy[now*2]+=lazy[now]; lazy[now*2+1]+=lazy[now];}
        lazy[now] = 0;
    }
    void update(int now, int s, int e, int l, int r, ll x){
        if(l>r) return;
        propagate(now,s,e);
        if(l<=s && e<=r){
            arr[now] += x;
            if(s!=e){ lazy[now*2]+=x; lazy[now*2+1]+=x;}
            return;
        }
        if(l>e || r<s) return;
        int m = s+e>>1;
        update(now*2,s,m,l,r,x); update(now*2+1,m+1,e,l,r,x);
        arr[now] = min(arr[now*2],arr[now*2+1]);
    }
    ll query(int now, int s, int e, int l, int r){
        if(l>r) return 2*inf;
        propagate(now,s,e);
        if(l<=s && e<=r) return arr[now];
        if(l>e || r<s) return 2*inf;
        int m = s+e>>1;
        return min(query(now*2,s,m,l,r) , query(now*2+1,m+1,e,l,r));
    }
} seg;

int main(){
    IO
    cin>>N;
    forf(i,1,N) cin>>arr[i];
    forf(i,1,N) seg.update(1,1,N,i,i,inf+i-1);
    arr[N+1] = -1;
    forf(i,1,N) if(arr[i] > 0) sum += arr[i];
    forf(i,1,N+1){
        if(arr[i] != -1) continue;
        if(i != N+1) bar.insert(i);
        int now = i-1;
        while(now >= 1 && arr[now] == 0) now--;
        if(now == 0 || arr[now] == -1) continue;
        arr[now]--; ans++; S.insert(now); seg.update(1,1,N,now,now,-inf);
        if(i != N+1) pq.insert({(i-now)*2, 1, now});
        grpnow++;

        while(now >= 1 && arr[now] >= 0) now--;
        forf(j, now+1, i-1) grp[j] = grpnow;
    }
    forf(i,1,N) if(arr[i] > 0) grpsum[grp[i]] += arr[i], nS.insert(i);

    forf(i,1,N){
        if(arr[i] > 0){
            lc[i] = inf, rc[i] = inf;
            if(bar.upper_bound(i) != bar.begin()) lc[i] = i - *prev(bar.upper_bound(i));
            if(bar.upper_bound(i) != bar.end()) rc[i] = *bar.upper_bound(i) - i;
            if(lc[i] < rc[i]) pq.insert({lc[i]*2, 0, i});
            else pq.insert({rc[i]*2, 1, i});
        }
    }

    while(sz(pq)){
        auto [v,c,i] = *pq.begin(); pq.erase(pq.begin());
        if(grpsum[grp[i]] == 0) continue;

        if(c == 0){
            int fst = 1;
            if(S.find(i) != S.end()) fst = 0;
            if(fst) seg.update(1,1,N,i,i,-inf);
            seg.update(1,1,N,i+fst,N,-v);

            if(seg.query(1,1,N,1,N) < 0){

                if(fst) seg.update(1,1,N,i,i,inf);
                seg.update(1,1,N,i+fst,N,v);
                continue;
            }

            S.insert(i); arr[i]--; ans++; grpsum[grp[i]]--;
            if(arr[i]) pq.insert({lc[i]*2, 0, i});
            else nS.erase(i);
        }
        else{
            ll prv = *prev(nS.upper_bound(i));
            int fst = 1;
            if(S.find(prv) != S.end()) fst = 0;

            if(fst) seg.update(1,1,N,prv,prv,-inf);
            seg.update(1,1,N,i,N,-v);

            if(seg.query(1,1,N,1,N) < 0){
                if(fst) seg.update(1,1,N,prv,prv,inf);
                seg.update(1,1,N,i,N,v);
                continue;
            }

            S.insert(prv); arr[prv]--; ans++; grpsum[grp[prv]]--;
            if(arr[prv] == 0) nS.erase(prv);
            if(prv == i) pq.insert({rc[i]*2, 1, i});
        }
    }

    cout<<sum-ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 25 / 25
• Subtask 5: 27 / 27