/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 4ms 532.0 KiB
#2 Wrong Answer 4ms 532.0 KiB
#3 Wrong Answer 1ms 532.0 KiB

Code

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using dt = array<int, 2>;

const int N = 2e5 + 9;
const int LG = 20;
int st[N][LG], a[N], b[N];
ll dp[N];

int combine(int x, int y) {
  return max(x, y);
}

void build(int n) {
  for (int i = 0; i < n; i++) st[i][0] = a[i], dp[i] = -1;
  for (int k = 1; k < LG; k++) {
    for (int i = 0; i + (1 << k) <= n; i++) {
      st[i][k] = combine(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
    }
  }
}

int query(int l, int r) {
  int k = 31 - __builtin_clz(r - l + 1);
  return combine(st[l][k], st[r - (1 << k) + 1][k]);
}

ll calc(int s, int n) {
	if (s >= n) return 0ll;
	int lo = s, hi = n - 1;
	while (lo <= hi) {
		int mid = (hi + lo) / 2;
		if (query(s, mid) == query(s, s)) {
			lo = mid + 1;
		} else {
			hi = mid - 1;
		}
	}
	return dp[s] = a[s] + calc(lo, n);
}

void test() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> b[i];
  }

  build(n);

  int x = 0;
  while (x < n) {
  	int lo = x, hi = n - 1;
  	while (lo <= hi) {
  		int mid = (hi + lo) / 2;
  		if (query(x, mid) == query(x, x)) {
  			lo = mid + 1;
  		} else {
  			hi = mid - 1;
  		}
  	}
  	int mx = -1e9;
  	for (int i = x; i <= hi; i++) {
  	  mx = max(mx, b[i]);
  	}
  	for (int i = x; i <= hi; i++) {
  	  b[i] = mx;
  	}
  	x = hi + 1;
  }

  ll mx = 0;
  for (int i = 0; i < n; i++) {
    mx = max(mx, calc(i, n));
  }
  ll tot = n;
  for (int i = 0; i < n; i++) {
  	if (calc(i, n) == mx) {
  		tot = min(tot, n*1ll - i);
  	}
  }
  cout << tot << "\n";
  
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T = 1;  
  cin >> T;
  for (int i = 1; i <= T; i++) {
    test();
  }
  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 17:44:55
Judged At
2025-09-02 17:44:55
Judged By
Score
1
Total Time
4ms
Peak Memory
532.0 KiB