제출 #533263

#제출 시각아이디문제언어결과실행 시간메모리
533263christinelynnMoney (IZhO17_money)C++17
100 / 100
1112 ms51488 KiB
#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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...