#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <cstring>
#include <unordered_map>
#include <iomanip>
#include <queue>
#include <map>
#include <sstream>
#include <stack>
#include <bitset>
using ll = long long;
using ld = long double;
using namespace std;
constexpr int nm = 400002;
int n, m;
ll a[nm], s[nm];
int previ[nm][20];
int getPrev(int i, int j) {
for (int u = 0; u < 20 && j && i >= 0; ++u) {
if ((j >> u) & 1) {
i = previ[i][u];
j &= ~(1 << u);
}
}
return i;
}
int f(int u, int v) {
int l = 1, r = v - u + 1;
while (l <= r) {
int mid = (l + r) / 2;
if (getPrev(v, mid) >= u - 1) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return l - 1;
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
unordered_map<ll, int> seen;
seen[0] = 0;
memset(previ, -1, sizeof(previ));
for (int i = 1; i <= n; ++i) {
cin >> a[i];
s[i] = s[i - 1] + a[i];
previ[i][0] = previ[i - 1][0];
if (seen.count(s[i])) {
previ[i][0] = max(seen[s[i]], previ[i][0]);
}
seen[s[i]] = i;
}
for (int j = 1; j < 20; ++j) {
for (int i = (1 << j); i <= n; ++i) {
int u = previ[i][j - 1];
if (u >= 0) previ[i][j] = previ[u][j - 1];
}
}
cin >> m;
int l, r;
for (int i = 0; i < m; ++i) {
cin >> l >> r;
cout << f(l, r) << "\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... |