/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 3ms 532.0 KiB
#3 Accepted 3ms 532.0 KiB
#4 Accepted 4ms 532.0 KiB
#5 Accepted 143ms 532.0 KiB
#6 Accepted 150ms 580.0 KiB
#7 Accepted 120ms 1.062 MiB
#8 Accepted 908ms 113.68 MiB
#9 Accepted 651ms 23.812 MiB
#10 Accepted 33ms 532.0 KiB
#11 Accepted 35ms 652.0 KiB
#12 Accepted 1189ms 110.43 MiB
#13 Accepted 172ms 532.0 KiB
#14 Accepted 493ms 77.379 MiB
#15 Accepted 501ms 61.797 MiB

Code

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int N = 2200005;

int z, n, a[N], c[N], M, res[N], id, d, i;
unordered_map<LL, int> mapa;
set<LL> vals;
LL sum[N], w[N];

void insert(int v, LL b) {
    int s = M + v;
    while (s) {
   	 w[s] = max(w[s], b);
   	 s /= 2;
    }
}
 
LL query(int a, int b) {
    int va = M + a, vb = M + b;
    LL wyn = w[va];
    if (va != vb) wyn = max(wyn, w[vb]);
    while (va / 2 != vb / 2) {
   	 if (va % 2 == 0) wyn = max(wyn, w[va + 1]);
   	 if (vb % 2 == 1) wyn = max(wyn, w[vb - 1]);
   	 va /= 2; vb /= 2;
    }
    return wyn;
}
 
void init(int a) {
    M = 1;
    while (M < a) M *= 2;
    for (int i = 1;i < 2 * M;i++) w[i] = -INF;
    M--;
}


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

cin >> z;
while(z--) {
	cin >> n;
	vals.clear();
	vals.insert(0);
	for (i=1;i<=n;i++) {
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
		vals.insert(sum[i]);
	}
	for (i=1;i<=n;i++) {
		cin >> c[i];
		vals.insert(sum[i] - c[i]);
	}
	d = 0;
	mapa.clear();
	for (auto& w : vals) mapa[w] = ++d;
	init(d);
	res[0] = 0;
	insert(mapa[0], 0);
	for (i=2;i<=n;i++) {
		id = mapa[sum[i] - c[i]];
		res[i] = query(1, id) + 1;
		id = mapa[sum[i - 1]];
		insert(id, res[i]);
		//cout << i << " " << res[i] << endl;
	}
	if (res[n] < 0 && n != 1) res[n] = -1;
	cout << res[n] << endl;
}
return 0;
}

Information

Submit By
Type
Submission
Problem
P1199 F. Roy and Path Game
Language
C++17 (G++ 13.2.0)
Submit At
2026-01-08 08:05:53
Judged At
2026-01-08 08:05:53
Judged By
Score
100
Total Time
1189ms
Peak Memory
113.68 MiB