Submission #1204805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204805		lighton	Tortoise (CEOI21_tortoise)	C++20	18 / 100	0 ms	328 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 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 inf;
        propagate(now,s,e);
        if(l<=s && e<=r) return arr[now];
        if(l>e || r<s) return 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--;
        grpnow++;
        forf(j, now + 1, i - 1) grp[j] = grpnow;
    }

    forf(i, 1, N) if (arr[i] > 0) nS.insert(i), grpsum[grp[i]] += arr[i];
    forf(i, 1, N) {
        if (arr[i] != -1) continue;
        if (nS.lower_bound(i) != nS.end()) {
            ll nxt = *nS.lower_bound(i);
            if (bar.upper_bound(i) == bar.end() || nxt < *bar.upper_bound(i)) pq.insert({2 * (nxt - i), nxt, 0});
        }
        if (nS.lower_bound(i) != nS.begin()) {
            ll prv = *prev(nS.lower_bound(i));
            if (bar.lower_bound(i) == bar.begin() || prv > *prev(bar.lower_bound(i))) {
                S.insert(prv); arr[prv]--; grpsum[grp[prv]]--; ans++; if (arr[prv] == 0) nS.erase(prv);
                seg.update(1,1,N,prv,prv,-inf);
                pq.insert({2 * (i - prv), prv, 1});
            }
        }
    }

    if(sz(nS)){
        ll prv = *prev(nS.lower_bound(N+1));
        if (bar.lower_bound(N+1) == bar.begin() || prv > *prev(bar.lower_bound(N+1))) {
            S.insert(prv); arr[prv]--; ans++; grpsum[grp[prv]]--; if (arr[prv] == 0) nS.erase(prv);
            seg.update(1,1,N,prv,prv,-inf);
        }
    }

    while(sz(pq)){
        auto [v,i,c] = *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] == 0) nS.erase(i);
            if(nS.lower_bound(i) == nS.end()) continue;

            ll nxt = *nS.lower_bound(i);
            if(bar.lower_bound(i) == bar.end() || nxt < *bar.lower_bound(i)){
                pq.insert({2*(nxt - *prev(bar.lower_bound(i))), nxt, 0});
            }
        }
        else{
            ll prv = *prev(nS.upper_bound(i));
            if(!(bar.lower_bound(i) == bar.begin() || prv > *prev(bar.lower_bound(i)))) continue;
            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);
            pq.insert({2*(*bar.lower_bound(i) - prv), prv, 1});
        }
    }

    cout<<sum-ans;
}

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