Submission #533570

#	Time	Username	Problem	Language	Result	Execution time	Memory
533570		makanhulia	Money (IZhO17_money)	C++17	100 / 100	1249 ms	55156 KiB

money

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
const ll MOD=1e9+7;
using namespace std;
ll N,a[1000005];
set <ll> s;
int main(){
  cin>>N;
  for(int i=1;i<=N;i++){
    cin>>a[i];
  }
  ll catat=1;
  ll temp=1e18;
  for(int i=1;i<=N;i++){
    if(i!=1){
      if(a[i-1]>a[i]||a[i]>temp){
        catat++;
        auto it=s.upper_bound(a[i]);
        if(it==s.end()){
          temp=1e18;
        }
        else{
          temp=*it;
        }
      }
    }
    s.insert(a[i]);
  }
//  cout<<endl;
  cout<<catat<<endl;
}

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