Submission #1114927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114927		Younis_Dwai	Money (IZhO17_money)	C++14	100 / 100	814 ms	61972 KiB

money

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define endl "\n"
#define F first
#define S second
#define pb push_back
//#define int long long
#define in insert
#define mid (l+r)/2
#define in insert
using namespace std;
const int N=1e6+6;
int b[N],R[N],n;
set<int> s;
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>b[i];
    R[n]=n;
    for(int i=n-1;i>=1;i--){
        if(b[i]<=b[i+1]) R[i]=R[i+1];
        else R[i]=i;
    }
    int ret=1,id=R[1];
    s.in(1e9+9);
    for(int i=1;i<=id;i++) s.in(b[i]);
    if(id!=n) ++ret;
    ++id;
    while(id<n){
          //cout<<" # "<<id<<endl;
               int nxt=*(s.upper_bound(b[id]));
               bool done=0;
               for(int j=id;j<=R[id];j++){
                   if(b[j]<=nxt){
                      s.in(b[j]);
                   }
                   else{
                      ++ret;
                      id=j;
                      done=1;
                      break;
                   }
               }
               if(!done){
                   id=R[id]+1;
                   if(id<=n) ++ret;
               }
    }
    cout<<ret<<endl;
    return 0;
}

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