Submission #1334069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1334069		Warinchai	Money (IZhO17_money)	C++20	45 / 100	1573 ms	51312 KiB

money

#include<bits/stdc++.h>
using namespace std;

int ar[1000005];
int inf=1e9;

multiset<int>ms;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>ar[i];
    for(int i=1;i<=n;i++){
        ms.insert(ar[i]);
    }
    int ans=0;
    for(int i=n;i>=1;){
        int mx=ar[i],mn=ar[i];
        //cerr<<"i:"<<i<<"\n";
        int cur=i;
        while(i>=1){
            if(ar[i]>ar[i+1]&&i!=cur)break;
            mn=min(mn,ar[i]);
            //cerr<<"erase:"<<ar[i]<<"\n";
            auto it=ms.upper_bound(mn);
            int val=inf;
            if(it!=ms.end())val=*it;
            //cerr<<"sz:"<<ms.size()<<"\n";
            if(val<mx){
                break;
            }
            ms.erase(ms.lower_bound(ar[i]));
            i--;
        }
        ans++;
        if(i==0)break;
    }
    cout<<ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 0 / 55