제출 #1285735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285735		teee	Tortoise (CEOI21_tortoise)	C++20	8 / 100	1 ms	580 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{
    multiset<T> pq;
    void push(T x){
        pq.insert(x);
    }
    void erase(T x) {
        if(!pq.count(x))return;
        pq.erase(pq.find(x));
    }
    int size(){
        return (int)pq.size();
    }
    T top(){
        return *pq.rbegin();
    }
    T bot(){
        return *pq.begin();
    }
    void clear(){
        pq.clear();
    }
};
erasePQ<int> mp;
erasePQ<int> now;
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;
    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{
                int tmp = now.top();
                sum-=tmp;
                mp.erase(tmp);
            }
            now.clear();
            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(mp.pq.count(w) != now.pq.count(w)){
            now.push(w);
        }
        while(now.size()!=0 && addTime+sum+min(-w,-now.top()+rgt[i]-i -w/2)>(i-1)*2){
            sum-=mp.top();
            now.erase(mp.top());
            mp.erase(mp.top());
        }
    }
    {
        if(pre==-1){
            add--;
        }else{
            int tmp = now.top();
            sum-=tmp;
            mp.erase(tmp);
        }
    }
    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