Submission #404470

#	Time	Username	Problem	Language	Result	Execution time	Memory
404470		rama_pang	Money (IZhO17_money)	C++17	100 / 100	330 ms	18900 KiB

money

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

class SegTree {
 public:
  int sz;
  vector<int> tree;

  SegTree(int sz) : sz(sz), tree(2 * sz, 0) {}

  void Update(int p, int x) {
    for (p += sz; p > 0; p /= 2) tree[p] += x;
  }

  int Query(int l, int r) {
    int res = 0 ;
    for (l += sz, r += sz; l < r; l /= 2, r /= 2) {
      if (l & 1) res += tree[l++];
      if (r & 1) res += tree[--r];
    }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }

  const int MAX = 1e6 + 5;
  SegTree seg(MAX);

  int ans = 0;
  for (int i = 0, j; i < N; i = j + 1) {
    ans += 1;
    for (j = i; j + 1 < N && A[j] <= A[j + 1] && seg.Query(A[i] + 1, A[j + 1]) == 0; j++);
    for (int k = i; k <= j; k++) {
      seg.Update(A[k], 1);
    }
  }

  cout << ans << '\n';
  return 0;
}

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