#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pli pair <ll, int>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()
const int NM = 4e5, LOG = 18, MOD = 5e4+3;
int RD = chrono::steady_clock::now().time_since_epoch().count();
struct hash_table{
vector <pli> arr[MOD];
int hash_val(ll x){
return ((x^RD)%MOD+MOD)%MOD;
}
void add(ll x, int y){
int tmp = hash_val(x);
for (int i = 0; i < isz(arr[tmp]); i++){
if (arr[tmp][i].fi == x){
arr[tmp][i].se = y;
return;
}
}
arr[tmp].push_back(mp(x, y));
}
int get(ll x){
int tmp = hash_val(x);
for (int i = 0; i < isz(arr[tmp]); i++){
if (arr[tmp][i].fi == x) return arr[tmp][i].se;
}
return -1;
}
} lst;
struct node{
int dep, jump;
};
int n, q, a[NM+5], nxt[NM+5];
ll pref[NM+5];
node T[NM+5];
void add_node(int u){
int p = nxt[u];
T[u].dep = T[p].dep+1;
if (T[p].dep-T[T[p].jump].dep == T[T[p].jump].dep-T[T[T[p].jump].jump].dep){
T[u].jump = T[T[p].jump].jump;
}
else{
T[u].jump = p;
}
}
int get(int l, int r){
int res = 0;
while (nxt[l] <= r){
if (T[l].jump <= r){
res += T[l].dep-T[T[l].jump].dep;
l = T[l].jump;
}
else{
res++;
l = nxt[l];
}
}
return res;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
pref[i] = pref[i-1]+a[i];
}
nxt[n+1] = n+1;
for (int i = n; i >= 0; i--){
nxt[i] = nxt[i+1];
int tmp = lst.get(pref[i]);
if (tmp != -1) nxt[i] = min(nxt[i], tmp);
lst.add(pref[i], i);
}
T[n+1].jump = n+1;
T[n+1].dep = 0;
for (int i = n; i >= 0; i--){
add_node(i);
}
cin >> q;
while (q--){
int l, r; cin >> l >> r;
cout << get(l-1, r) << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
6748 KB |
Output is correct |
2 |
Correct |
3 ms |
6748 KB |
Output is correct |
3 |
Correct |
3 ms |
6748 KB |
Output is correct |
4 |
Correct |
3 ms |
6748 KB |
Output is correct |
5 |
Correct |
3 ms |
6748 KB |
Output is correct |
6 |
Correct |
4 ms |
6748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
6748 KB |
Output is correct |
2 |
Correct |
3 ms |
6748 KB |
Output is correct |
3 |
Correct |
3 ms |
6748 KB |
Output is correct |
4 |
Correct |
3 ms |
6748 KB |
Output is correct |
5 |
Correct |
3 ms |
6748 KB |
Output is correct |
6 |
Correct |
4 ms |
6748 KB |
Output is correct |
7 |
Correct |
39 ms |
11312 KB |
Output is correct |
8 |
Correct |
36 ms |
11612 KB |
Output is correct |
9 |
Correct |
41 ms |
10444 KB |
Output is correct |
10 |
Correct |
40 ms |
11100 KB |
Output is correct |
11 |
Correct |
39 ms |
11260 KB |
Output is correct |
12 |
Correct |
39 ms |
10324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
6748 KB |
Output is correct |
2 |
Correct |
3 ms |
6748 KB |
Output is correct |
3 |
Correct |
3 ms |
6748 KB |
Output is correct |
4 |
Correct |
3 ms |
6748 KB |
Output is correct |
5 |
Correct |
3 ms |
6748 KB |
Output is correct |
6 |
Correct |
4 ms |
6748 KB |
Output is correct |
7 |
Correct |
39 ms |
11312 KB |
Output is correct |
8 |
Correct |
36 ms |
11612 KB |
Output is correct |
9 |
Correct |
41 ms |
10444 KB |
Output is correct |
10 |
Correct |
40 ms |
11100 KB |
Output is correct |
11 |
Correct |
39 ms |
11260 KB |
Output is correct |
12 |
Correct |
39 ms |
10324 KB |
Output is correct |
13 |
Correct |
181 ms |
16976 KB |
Output is correct |
14 |
Correct |
165 ms |
17492 KB |
Output is correct |
15 |
Correct |
187 ms |
13648 KB |
Output is correct |
16 |
Correct |
179 ms |
17944 KB |
Output is correct |
17 |
Correct |
173 ms |
20104 KB |
Output is correct |
18 |
Correct |
192 ms |
17492 KB |
Output is correct |