Submission #533234

#	Time	Username	Problem	Language	Result	Execution time	Memory
533234		devariaota	Money (IZhO17_money)	C++17	45 / 100	1577 ms	11480 KiB

money

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

int n;
int lst[1000005];
vector<int> arr;
map <int, bool> mp; 

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) {
    //cout << "::" << l << endl;
    ans++;
    int loc = binser(lst[l]);
    int r = l + 1;
    while(r <= n && lst[r] >= lst[r - 1]) {
      int loc1 = binser(lst[r]);
      
      //cout << r << " " << loc << " " << loc1 << endl;
      if (loc1 >= 0 && lst[r] == arr[loc1] && loc == loc1 - 1) {
        loc1--;
      }
      if (loc == loc1) {
        r++;
      }
      else {
        break;
      }
    }
    for(int i = l; i < r; i++) {
      if (mp.count(lst[i])) {
        continue;
      }
      mp.insert({lst[i], true});
      arr.push_back(lst[i]);
    }
    sort(arr.begin(), arr.end());
    l = r;
  }
  cout << ans;
}

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