Submission #533263

#	Time	Username	Problem	Language	Result	Execution time	Memory
533263		christinelynn	Money (IZhO17_money)	C++17	100 / 100	1112 ms	51488 KiB

money

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

int n;
int arr[1000005];
set<int> st;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> arr[i];
  }
  
  int l = 1;
  int ans = 0;
  while(l <= n) {
    //cout << "::" << l << endl;
    ans++;
    auto loc = st.lower_bound(arr[l]);
    auto opt = st.upper_bound(arr[l]);
    int r = l + 1;
    while(r <= n && arr[r] >= arr[r - 1]) {
      auto loc1 = st.lower_bound(arr[r]);
      
      //cout << r << " " << loc << " " << loc1 << endl;
      //cout << *loc << " " << *opt << " " << *loc1 << endl;
      if (*loc == *loc1 || *opt == *loc1) {
        r++;
      }
      else {
        break;
      }
    }
    for(int i = l; i < r; i++) {
      st.insert(arr[i]);
    }
    l = r;
  }
  cout << ans << "\n";
}

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