/ SeriousOJ /

Record Detail

Memory Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 3ms 536.0 KiB
#3 Accepted 4ms 532.0 KiB
#4 Accepted 6ms 532.0 KiB
#5 Accepted 113ms 644.0 KiB
#6 Accepted 267ms 19.309 MiB
#7 Accepted 117ms 1.52 MiB
#8 Memory Exceeded ≥1128ms ≥128.016 MiB
#9 Accepted 781ms 53.625 MiB
#10 Accepted 46ms 5.102 MiB
#11 Accepted 50ms 5.285 MiB
#12 Wrong Answer 919ms 108.676 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 = 1200005;

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;
	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:04:59
Judged At
2026-01-08 08:04:59
Judged By
Score
60
Total Time
≥1128ms
Peak Memory
≥128.016 MiB