Submission #1285707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285707		teee	Tortoise (CEOI21_tortoise)	C++20	8 / 100	1 ms	576 KiB

tortoise

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#include <queue>
#include <set>
#include <array>
#include <algorithm>
#include <random>
#include <bitset>
#include "array"
#include <chrono>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag,
//        tree_order_statistics_node_update> pds;
#define all(x)x.begin(),x.end()
#define pack(x)sort(all(x));x.erase(unique(all(x)),x.end())
#define gi(x, v)lower_bound(all(x),v)-x.begin()
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; }
using ll = long long;
using ld = long double;
using tu = array<int, 2>;
#define int ll
template<class T>
struct erasePQ{
    priority_queue<T> pq,era;
    void push(T x){
        pq.push(x);
    }
    void upd(){
        while (!era.empty() && pq.top() == era.top()){
            pq.pop();
            era.pop();
        }
    }
    void pop(){
        upd();
        pq.pop();
    }
    void erase(T x) {
        era.push(x);
    }
    int size(){
        return (int)pq.size()-(int)era.size();
    }
    T top(){
        upd();
        return pq.top();
    }
    void clear(){
        pq = priority_queue<T>();
        era = priority_queue<T>();
    }
};
erasePQ<int> mp;
int arr[500'010];
int lft[500'010];
int rgt[500'010];
int last[500'010];
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,a;
    int ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        if(arr[i]!=-1)ans+=arr[i];
    }

    int idx=-1e9;
    for(int i=1;i<=n;i++){
        lft[i]=idx;
        if(arr[i]==-1)idx=i;
    }idx=1e9;
    for(int i=n;i>=1;i--){
        rgt[i]=idx;
        if(arr[i]==-1)idx=i;
    }

    int add=1;
    int pre=-1;
    bool erased = false;
    int sum = 0;
    int addTime = -1;
    int cnt=0;
    for(int i=1;i<=n;i++){
        addTime++;
        if(arr[i]==-1){
            cnt++;
            if(pre==-1){
                add--;
            }else if(!erased){
                sum-=pre;
                mp.erase(pre);
            }
            erased=false;
            pre=-1;
            add++;
            continue;
        }
        if(arr[i]==0)continue;
        int w = min(rgt[i]-i,i-lft[i])*2;
        pre=max(pre,w);
        last[w]=cnt;
        while(arr[i]){
            mp.push(w);
            sum+=w;
            arr[i]--;
        }
        while(addTime+sum - w/2>(i-1)*2){
            sum-=mp.top();
            if(last[mp.top()]==cnt){
                erased=true;
            }
            mp.erase(mp.top());
        }
    }
    {
        if(pre==-1){
            add--;
        }
    }
    cout<<ans-mp.size()-add;

}

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