Submission #710241

#	Time	Username	Problem	Language	Result	Execution time	Memory
710241		safaricola	Money (IZhO17_money)	C++17	100 / 100	1074 ms	51276 KiB

money

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pi pair <int, int>
#define pii pair <pi, int>
#define rep(i,n) for(ll i = 0; i < n; i++)
#define fi first
#define se second
using namespace std;
#define debug(x) cout<<#x<<' '<<x<<endl;
int n, a[1000010],i,ans;
bool vis[1000010];
set<int> s;
int main(){
   ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
   cin>>n;
   rep(i,n)cin>>a[i];
   while(i<n){
      auto it= s.upper_bound(a[i]);
      s.insert(a[i]);
      while(i+1<n&&a[i+1]>=a[i]&&(it==s.end()||a[i+1]<=*it)){
         i++;s.insert(a[i]);
      }
      i++;
      ans++;
   }
   cout<<ans;
}

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