# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
646679 | Vanilla | Sum Zero (RMI20_sumzero) | C++17 | 592 ms | 27828 KiB |
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>
using namespace std;
typedef long long int64;
const int maxn = 4e5 + 5;
const int lg = 10;
vector <int> jump [lg];
int ps [maxn];
int64 pref [maxn];
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int n;
cin >> n;
int64 s = 0, a = 0;
for (int i = 0; i < lg; i++) jump[i].push_back(0);
for (int i = 1; i <= n; i++) jump[0].push_back(n + 1);
for (int i = 0; i < maxn; i++) ps[i] = -1;
vector <int64> norm = {0};
for (int i = 1; i <= n; i++){
cin >> a;
pref[i] = pref[i-1] + a;
norm.push_back(pref[i]);
}
sort(norm.begin(), norm.end());
ps[lower_bound(norm.begin(), norm.end(), 0) - norm.begin()] = 0;
for (int i = 1; i <= n; i++){
int k = lower_bound(norm.begin(), norm.end(), pref[i]) - norm.begin();
if (ps[k] != -1) {
jump[0][ps[k] + 1] = i;
}
ps[k] = i;
}
for (int i = n - 1; i >= 1; i--){
jump[0][i] = min(jump[0][i], jump[0][i + 1]);
}
for (int k = 1; k < lg; k++){
for (int i = 1; i < jump[k-1].size(); i++){
int p1 = jump[k-1][i] + 1;
if (p1 >= jump[k-1].size()) break;
jump[k].push_back(jump[k-1][p1]);
}
}
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
int rs = 0;
for (int i = lg - 1; i >= 0; i--){
while (jump[i].size() > l && jump[i][l] <= r) {
rs+=(1 << i);
l = jump[i][l] + 1;
}
}
cout << rs << "\n";
};
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |