/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 1ms 532.0 KiB
#3 Accepted 1ms 532.0 KiB
#4 Accepted 1ms 532.0 KiB
#5 Accepted 1ms 532.0 KiB
#6 Accepted 1ms 492.0 KiB
#7 Accepted 1ms 532.0 KiB
#8 Accepted 1ms 320.0 KiB
#9 Accepted 1ms 324.0 KiB
#10 Accepted 1ms 532.0 KiB
#11 Accepted 1ms 324.0 KiB
#12 Accepted 1ms 532.0 KiB
#13 Accepted 1ms 532.0 KiB
#14 Accepted 2ms 532.0 KiB
#15 Accepted 1ms 532.0 KiB
#16 Accepted 1ms 764.0 KiB
#17 Accepted 1ms 532.0 KiB
#18 Accepted 1ms 320.0 KiB
#19 Accepted 2ms 532.0 KiB
#20 Accepted 1ms 532.0 KiB
#21 Accepted 1ms 532.0 KiB
#22 Accepted 4ms 532.0 KiB
#23 Accepted 5ms 564.0 KiB
#24 Accepted 4ms 532.0 KiB
#25 Accepted 5ms 492.0 KiB
#26 Accepted 2ms 532.0 KiB
#27 Accepted 1ms 532.0 KiB
#28 Accepted 1ms 532.0 KiB
#29 Accepted 1ms 536.0 KiB
#30 Accepted 1ms 532.0 KiB
#31 Accepted 1ms 532.0 KiB
#32 Accepted 1ms 532.0 KiB
#33 Accepted 1ms 500.0 KiB
#34 Accepted 1ms 520.0 KiB
#35 Accepted 1ms 376.0 KiB
#36 Accepted 1ms 348.0 KiB
#37 Accepted 1ms 324.0 KiB
#38 Accepted 1ms 532.0 KiB
#39 Accepted 1ms 532.0 KiB
#40 Accepted 1ms 532.0 KiB
#41 Accepted 2ms 324.0 KiB
#42 Accepted 3ms 532.0 KiB
#43 Accepted 4ms 532.0 KiB
#44 Accepted 4ms 532.0 KiB
#45 Accepted 5ms 560.0 KiB
#46 Accepted 5ms 532.0 KiB
#47 Accepted 5ms 368.0 KiB
#48 Accepted 4ms 532.0 KiB
#49 Accepted 5ms 532.0 KiB
#50 Accepted 4ms 532.0 KiB
#51 Accepted 4ms 532.0 KiB
#52 Accepted 4ms 532.0 KiB
#53 Accepted 3ms 532.0 KiB
#54 Accepted 3ms 520.0 KiB
#55 Accepted 3ms 532.0 KiB
#56 Accepted 3ms 532.0 KiB
#57 Accepted 3ms 532.0 KiB
#58 Accepted 4ms 740.0 KiB
#59 Accepted 4ms 532.0 KiB
#60 Accepted 5ms 444.0 KiB
#61 Accepted 4ms 532.0 KiB
#62 Accepted 5ms 352.0 KiB
#63 Accepted 4ms 532.0 KiB
#64 Accepted 4ms 532.0 KiB
#65 Accepted 4ms 532.0 KiB
#66 Accepted 5ms 532.0 KiB
#67 Accepted 5ms 368.0 KiB
#68 Accepted 4ms 324.0 KiB
#69 Accepted 4ms 532.0 KiB
#70 Accepted 4ms 536.0 KiB
#71 Accepted 5ms 444.0 KiB
#72 Accepted 4ms 320.0 KiB
#73 Accepted 4ms 532.0 KiB
#74 Accepted 4ms 324.0 KiB
#75 Accepted 5ms 488.0 KiB
#76 Accepted 4ms 532.0 KiB
#77 Accepted 4ms 532.0 KiB
#78 Accepted 5ms 484.0 KiB
#79 Accepted 4ms 532.0 KiB
#80 Accepted 4ms 532.0 KiB
#81 Accepted 54ms 1.27 MiB
#82 Accepted 54ms 1.27 MiB
#83 Accepted 64ms 1.27 MiB
#84 Accepted 56ms 1.355 MiB
#85 Accepted 60ms 1.27 MiB
#86 Accepted 57ms 1.309 MiB
#87 Accepted 63ms 1.27 MiB
#88 Accepted 60ms 1.355 MiB
#89 Accepted 52ms 1.355 MiB
#90 Accepted 64ms 1.27 MiB
#91 Accepted 76ms 7.52 MiB
#92 Accepted 90ms 7.566 MiB
#93 Accepted 92ms 7.52 MiB
#94 Accepted 38ms 7.57 MiB
#95 Accepted 39ms 7.52 MiB
#96 Accepted 64ms 7.523 MiB
#97 Accepted 69ms 7.582 MiB
#98 Accepted 38ms 7.52 MiB
#99 Accepted 40ms 7.562 MiB
#100 Accepted 61ms 7.57 MiB

Code

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

template <class T> struct SegmentTreeIterative {
  int n = 1;
  vector<T> st;
  SegmentTreeIterative() {}
  SegmentTreeIterative(int n) { Initial(n); }
  SegmentTreeIterative(vector<int>& a) {
    Initial((int)a.size() - 1);
    Build(a);
  }
  void Initial(int _n) {
    n = _n;
    int tree_size = 1;
    while (tree_size <= n) tree_size *= 2;
    st.resize(tree_size * 2);
  }
  T neutral = 0;
  T Merge(T& a, T& b) {
    return max(a, b);
  }
  void Build(vector<int>& a) {
    for (int i = 1; i <= n; ++i) {
      st[n + i] = a[i];
    }
    for (int u = n - 1; u > 0; --u) {
      st[u] = Merge(st[u << 1], st[u << 1 | 1]);
    }
  }
  void Update(int idx, T val) {
    st[idx += n] = val;
    for (idx /= 2; idx; idx /= 2) {
      st[idx] = Merge(st[idx << 1], st[idx << 1 | 1]);
    }
  }
  T Query(int l, int r) {
    T res = neutral;
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) res = Merge(res, st[l++]);
      if (r & 1) res = Merge(res, st[--r]);
    }
    return res;
  }
};

void solve() {
  int n;
  cin >> n;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  vector<int> b(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> b[i];
  }
  SegmentTreeIterative<int64_t> sg(n + 9);
  vector<int64_t> mx(n + 1);
  int64_t gMx = 0;
  for (int i = n; i > 0; i--) {
    mx[i] = sg.Query(a[i] + 1, n + 1) + b[i];
    if (sg.Query(a[i], a[i]) < mx[i]) {
      sg.Update(a[i], mx[i]);
    }
    gMx = max(gMx, mx[i]);
  }
  int i = n;
  while (i > 0 && gMx != mx[i]) i--;
  cout << n - i + 1 << '\n';
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int t = 1;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    solve();
  }
  return 0;
}

Information

Submit By
Type
Submission
Problem
P1224 Maximize the max
Contest
LUCC Presents Intra LU Junior Programming Contest - Replay
Language
C++17 (G++ 13.2.0)
Submit At
2025-09-02 16:59:21
Judged At
2025-09-02 16:59:21
Judged By
Score
100
Total Time
92ms
Peak Memory
7.582 MiB