Submission #533225

#	Time	Username	Problem	Language	Result	Execution time	Memory
533225		devariaota	Money (IZhO17_money)	C++17	0 / 100	1 ms	208 KiB

money

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

int n;
int lst[1000005];
vector<int> arr;

int binser(int x) {
  int l = 0, r = arr.size(), ans = -1;
  r--;
  while(l <= r) {
    int mid = (l + r) / 2;
    if (arr[mid] <= x) {
      ans = mid;
      l = mid + 1;
    }
    else {
      r = mid - 1;
    }
  }
  return ans;
}

int main() {
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> lst[i];
  }
  
  int l = 1;
  int ans = 0;
  while(l <= n) {
    ans++;
    int loc = binser(lst[l]);
    int r = l;
    while(r + 1 <= n && lst[r + 1] >= lst[r] && loc == binser(lst[r + 1])) {
      r++;
    }
    for(int i = l; i <= r; i++) {
      arr.push_back(lst[i]);
    }
    sort(arr.begin(), arr.end());
    //cout << l << " " << r << endl;
    l = r + 1;
  }
  cout << ans;
}

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