/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 3ms 3.777 MiB
#2 Accepted 3ms 3.777 MiB
#3 Accepted 3ms 3.75 MiB
#4 Accepted 3ms 3.777 MiB
#5 Accepted 3ms 3.527 MiB
#6 Accepted 3ms 3.605 MiB
#7 Accepted 3ms 3.715 MiB
#8 Accepted 3ms 3.527 MiB
#9 Accepted 3ms 3.371 MiB
#10 Accepted 4ms 3.777 MiB
#11 Accepted 3ms 3.574 MiB
#12 Accepted 3ms 3.527 MiB
#13 Accepted 3ms 3.777 MiB
#14 Accepted 3ms 3.574 MiB
#15 Accepted 3ms 3.527 MiB
#16 Accepted 3ms 3.527 MiB
#17 Accepted 3ms 3.527 MiB
#18 Accepted 3ms 3.527 MiB
#19 Accepted 3ms 3.527 MiB
#20 Accepted 4ms 3.742 MiB
#21 Accepted 3ms 3.527 MiB
#22 Accepted 3ms 3.777 MiB
#23 Accepted 3ms 3.57 MiB
#24 Accepted 3ms 3.527 MiB
#25 Accepted 3ms 3.793 MiB
#26 Accepted 3ms 3.527 MiB
#27 Accepted 3ms 3.777 MiB
#28 Accepted 3ms 3.527 MiB
#29 Accepted 3ms 3.527 MiB
#30 Accepted 3ms 3.527 MiB
#31 Accepted 3ms 3.527 MiB
#32 Accepted 3ms 3.527 MiB
#33 Accepted 3ms 3.527 MiB
#34 Accepted 3ms 3.574 MiB
#35 Accepted 3ms 3.379 MiB
#36 Accepted 3ms 3.527 MiB
#37 Accepted 3ms 3.527 MiB
#38 Accepted 3ms 3.527 MiB
#39 Accepted 3ms 3.527 MiB
#40 Accepted 4ms 3.777 MiB
#41 Accepted 4ms 3.527 MiB
#42 Accepted 4ms 3.527 MiB
#43 Accepted 4ms 3.527 MiB
#44 Accepted 4ms 3.777 MiB
#45 Accepted 4ms 3.777 MiB
#46 Accepted 4ms 3.527 MiB
#47 Accepted 4ms 3.777 MiB
#48 Accepted 4ms 3.527 MiB
#49 Accepted 4ms 3.574 MiB
#50 Accepted 4ms 3.781 MiB
#51 Accepted 4ms 3.777 MiB
#52 Accepted 4ms 3.527 MiB
#53 Accepted 4ms 3.527 MiB
#54 Accepted 4ms 3.527 MiB
#55 Accepted 4ms 3.527 MiB
#56 Accepted 3ms 3.527 MiB
#57 Accepted 4ms 3.777 MiB
#58 Accepted 4ms 3.586 MiB
#59 Accepted 4ms 3.797 MiB
#60 Accepted 3ms 3.777 MiB
#61 Accepted 4ms 3.777 MiB
#62 Accepted 4ms 3.527 MiB
#63 Accepted 4ms 3.527 MiB
#64 Accepted 4ms 3.777 MiB
#65 Accepted 4ms 3.527 MiB
#66 Accepted 4ms 3.574 MiB
#67 Accepted 4ms 3.527 MiB
#68 Accepted 4ms 3.777 MiB
#69 Accepted 4ms 3.527 MiB
#70 Accepted 4ms 3.777 MiB
#71 Accepted 5ms 3.715 MiB
#72 Accepted 5ms 3.777 MiB
#73 Accepted 5ms 3.613 MiB
#74 Accepted 5ms 3.527 MiB
#75 Accepted 5ms 3.566 MiB
#76 Accepted 5ms 3.777 MiB
#77 Accepted 5ms 3.52 MiB
#78 Accepted 5ms 3.777 MiB
#79 Accepted 5ms 3.777 MiB
#80 Accepted 5ms 3.527 MiB
#81 Accepted 5ms 3.77 MiB
#82 Accepted 5ms 3.566 MiB
#83 Accepted 5ms 3.777 MiB
#84 Accepted 5ms 3.582 MiB
#85 Accepted 5ms 3.664 MiB
#86 Accepted 5ms 3.777 MiB
#87 Accepted 5ms 3.777 MiB
#88 Accepted 5ms 3.777 MiB
#89 Accepted 5ms 3.77 MiB
#90 Accepted 7ms 3.777 MiB
#91 Accepted 29ms 5.066 MiB
#92 Accepted 27ms 4.961 MiB
#93 Accepted 27ms 5.07 MiB
#94 Accepted 26ms 5.066 MiB
#95 Accepted 23ms 5.113 MiB
#96 Accepted 20ms 5.066 MiB
#97 Accepted 18ms 5.02 MiB
#98 Accepted 18ms 5.066 MiB
#99 Accepted 17ms 5.02 MiB
#100 Accepted 17ms 5.07 MiB

Code

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

template<class Fun> class y_combinator_result {
  Fun fun_;
public:
  template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
  template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename... Args> ostream& operator<<(ostream& os, const tuple<Args...>& t) { os << '('; apply([&os](const Args&... args) { size_t n = 0; ((os << args << (++n != sizeof...(Args) ? ", " : "")), ...); }, t); return os << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

template<typename T>ostream& operator<<(ostream& os, queue<T>& _q) { queue<T> q = _q; os << '{'; string sep; while (!q.empty()) { os << sep << q.front(); sep = ", "; q.pop(); } return os << '}';}
template<typename T>ostream& operator<<(ostream& os, stack<T> st) { os << '{'; string sep; while (!st.empty()) { os << sep << st.top(); sep = ", "; st.pop(); } return os << '}';}
template<typename T, typename Container, typename Compare>ostream& operator<<(ostream& os, priority_queue<T, Container, Compare> pq) { os << '{'; string sep; while (!pq.empty()) { os << sep << pq.top(); sep = ", "; pq.pop(); } return os << '}';}
template<size_t N>ostream& operator<<(ostream& os, const bitset<N>& bs) { return os << bs.to_string();}

void debug_out() { cout << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cout << ' ' << H; debug_out(T...); }
#ifdef LOCAL_DEBUG
  #define debug(...) cout << "[Line " <<  __LINE__ << "] (" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
  #define debug(...)
#endif

/*
  
*/

const int MAXN = 2e5 + 5;

template <class T>
struct BIT { //1-indexed
  int n; vector<T> t;
  BIT() {}
  BIT(int _n) {
    n = _n; t.assign(n + 1, 0);
  }
  T query(int i) {
    T ans = 0;
    for (; i >= 1; i -= (i & -i)) ans += t[i];
    return ans;
  }
  void upd(int i, T val) {
    if (i <= 0) return;
    for (; i <= n; i += (i & -i)) t[i] += val;
  }
  void upd(int l, int r, T val) {
    upd(l, val);
    upd(r + 1, -val);
  }
  T query(int l, int r) {
    return query(r) - query(l - 1);
  }
};

void run_case() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i]++;
  }
  
  BIT<int> bit(MAXN);
  vector<int> left(n);
  for (int i = 0; i < n; i++) {
    left[i] = bit.query(a[i]);
    bit.upd(a[i], 1);
  }
  
  bit = BIT<int>(MAXN);
  vector<int> right(n);
  for (int i = n - 1; i >= 0; i--) {
    right[i] = (n - 1 - i) - bit.query(a[i] - 1);
    bit.upd(a[i], 1);
  }
  
  int res = 0;
  for (int i = 0; i < n; i++) {
    res += max(left[i], right[i]) >= a[i] - 1;
  }
  cout << res << '\n';
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin.exceptions(cin.failbit);

  int T = 1;
  // cin >> T;
  for (int t = 1; t <= T; t++) {
    // cout << "Case #" << t << ": ";
    run_case();
  }

  return 0;
}

Information

Submit By
Type
Submission
Problem
P1184 The Curious Kid and the Number Game
Contest
Brain Booster #9
Language
C++17 (G++ 13.2.0)
Submit At
2025-04-06 17:00:10
Judged At
2025-04-06 17:00:10
Judged By
Score
100
Total Time
29ms
Peak Memory
5.113 MiB