// rshohruh
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main(){
int n; cin >> n;
vector<int> a(n+1);
for(int i = 1; i <= n; ++i) cin >> a[i];
int log = 1;
while((1<<log) <= n) log ++;
vector up(log, vector(n+1, -1));
map<int, int> mp;
mp[0] = 0;
for(int i = 1, cur = 0, id = -1; i <= n; ++i) {
cur += a[i];
if(mp.count(cur)) id = max(id, mp[cur]);
up[0][i] = id;
for(int j = 1; j < log; ++j) {
if(up[j-1][i] != -1)
up[j][i] = up[j-1][up[j-1][i]];
}
mp[cur] = i;
}
int q; cin >> q;
while(q--) {
int l, r; cin >> l >> r;
int ans = 0;
for(int i = log-1; i >= 0; --i) {
if(up[i][r] + 1 >= l) {
ans += (1<<i);
r = up[i][r];
}
}
cout << ans << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |