#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
//#define endl '\n'
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 4e5 + 2;
const int K = 128; // base
const int L = 3; // K^L >= N
int a[N];
int go[N][L];
void solve(){
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
unordered_map<ll, int> mp;
mp[0] = n + 1;
ll sum = 0;
for (int i = n; i >= 1; i--){
sum += a[i];
if (mp.find(sum) != mp.end()){
a[i] = mp[sum];
} else {
a[i] = -1;
}
mp[sum] = i;
}
int where = -1;
for (int i = n; i >= 1; i--){
if (a[i] != -1){
if (where == -1){
where = a[i];
} else {
where = min(where, a[i]);
}
}
go[i][0] = where;
}
go[n + 1][0] = -1;
for (int j = 1; j < L; j++){
for (int i = 1; i <= n + 1; i++){
int v = i;
for (int t = 0; t < K && v != -1; t++){
v = go[v][j - 1];
}
go[i][j] = v;
}
}
vector<int> pw(L);
pw[0] = 1;
for (int i = 1; i < L; i++) pw[i] = pw[i - 1] * K;
int q;
cin >> q;
while (q--){
int l, r;
cin >> l >> r;
++r;
int ans = 0;
int v = l;
for (int i = L - 1; i >= 0; i--){
while (go[v][i] != -1 && go[v][i] <= r){
v = go[v][i];
ans += pw[i];
}
}
cout << ans << "\n";
}
}
int main(){
clock_t startTime = clock();
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int test_cases = 1;
//cin >> test_cases;
for (int test = 1; test <= test_cases; test++){
//cout << (solve() ? "YES" : "NO") << endl;
solve();
}
#ifdef LOCAL
cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif
return 0;
}
Compilation message
sumzero.cpp: In function 'int main()':
sumzero.cpp:98:13: warning: unused variable 'startTime' [-Wunused-variable]
98 | clock_t startTime = clock();
| ^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
468 KB |
Output is correct |
2 |
Correct |
3 ms |
468 KB |
Output is correct |
3 |
Correct |
4 ms |
468 KB |
Output is correct |
4 |
Correct |
4 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
468 KB |
Output is correct |
6 |
Correct |
4 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
468 KB |
Output is correct |
2 |
Correct |
3 ms |
468 KB |
Output is correct |
3 |
Correct |
4 ms |
468 KB |
Output is correct |
4 |
Correct |
4 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
468 KB |
Output is correct |
6 |
Correct |
4 ms |
468 KB |
Output is correct |
7 |
Correct |
149 ms |
3904 KB |
Output is correct |
8 |
Correct |
85 ms |
4440 KB |
Output is correct |
9 |
Correct |
136 ms |
2944 KB |
Output is correct |
10 |
Correct |
149 ms |
3916 KB |
Output is correct |
11 |
Correct |
84 ms |
3740 KB |
Output is correct |
12 |
Correct |
139 ms |
2900 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
468 KB |
Output is correct |
2 |
Correct |
3 ms |
468 KB |
Output is correct |
3 |
Correct |
4 ms |
468 KB |
Output is correct |
4 |
Correct |
4 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
468 KB |
Output is correct |
6 |
Correct |
4 ms |
468 KB |
Output is correct |
7 |
Correct |
149 ms |
3904 KB |
Output is correct |
8 |
Correct |
85 ms |
4440 KB |
Output is correct |
9 |
Correct |
136 ms |
2944 KB |
Output is correct |
10 |
Correct |
149 ms |
3916 KB |
Output is correct |
11 |
Correct |
84 ms |
3740 KB |
Output is correct |
12 |
Correct |
139 ms |
2900 KB |
Output is correct |
13 |
Correct |
834 ms |
15028 KB |
Output is correct |
14 |
Correct |
528 ms |
17336 KB |
Output is correct |
15 |
Correct |
942 ms |
9340 KB |
Output is correct |
16 |
Correct |
837 ms |
17356 KB |
Output is correct |
17 |
Correct |
601 ms |
14372 KB |
Output is correct |
18 |
Correct |
970 ms |
9332 KB |
Output is correct |