Submission #937397

#	Time	Username	Problem	Language	Result	Execution time	Memory
937397		stefanneagu	Money (IZhO17_money)	C++17	100 / 100	961 ms	58248 KiB

money

#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e6 + 1;

int v[nmax];

int main() {
  int n;
  cin >> n;
  for(int i = 1; i <= n; i ++) {
    cin >> v[i];
  }
  set<int> s;
  s.insert(1e9);
  int i = 1, ans = 0;
  while(i <= n) {
    int x = *s.upper_bound(v[i]);
    s.insert(v[i]);
    while(i < n && v[i] <= v[i + 1] && v[i + 1] <= x) {
      i ++;
      s.insert(v[i]);
    }
    i ++;
    ans ++;
  }
  cout << ans;
  return 0;
}

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