This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
#define int long long
#define inf 1e18
#define ick cout<<"ickbmi32.9\n"
using namespace std;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
int arr[n + 5];
int ps[n + 5];
int next[n + 5];
map<int, int> la;
ps[0] = 0;
for(int i = 1; i <= n; i++) {
cin >> arr[i];
ps[i] = ps[i - 1] + arr[i];
next[i] = n + 1;
if(la[ps[i]] != 0 || ps[i] == 0) {
next[la[ps[i]] + 1] = min(next[la[ps[i]] + 1], i);
}
la[ps[i]] = i;
}
for(int i = n - 1; i >= 1; i--) {
next[i] = min(next[i], next[i + 1]);
}
// for(int i = 1; i <= n; i++) {
// cout << next[i] << ' ';
// }cout << '\n'; //return 0;
int sps[n + 5][25];
next[n + 1] = n + 1;
next[n + 2] = n + 1;
for(int i = 1; i <= n + 2; i++) {
sps[i][0] = next[i];
}
for(int j = 1; j < 20; j++) {
for(int i = 1; i <= n + 2; i++) {
sps[i][j] = sps[sps[i][j - 1] + 1][j - 1];
if(sps[i][j] > n) sps[i][j] = n + 1;
// cout << sps[i][j] << ' ';
}
// cout << '\n';
}//return 0;
int q;
cin >> q;
while(q--) {
int l, r;
cin >> l >> r;
int ans = 0;
for(int i = 19; i >= 0; i--) {
if(sps[l][i] <= r) {
ans += (1 << i);
l = sps[l][i] + 1;
}
}
cout << ans << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |