이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define sz(x) int(x.size())
#define pb push_back
using ll = long long;
template<class T> using V = vector<T>;
using vl = V<ll>;
const int nax = 4e5+5;
const int K = 26;
const int LG = 4;
int nxt[nax][LG], pw[LG];
int A[nax], N;
unordered_map<ll, int> lst;
int main() {
cin.tie(0)->sync_with_stdio(0);
for(int j = 0; j < LG; j++) {
for(int i = 0; i < nax; i++) nxt[i][j] = nax - 1;
pw[j] = (j ? pw[j - 1] * K : 1);
}
cin >> N;
ll S = 0;
for(int i = 0; i < N; i++) {
cin >> A[i];
S += A[i];
}
lst[S] = N;
for(int i = N - 1; i >= 0; i--) {
S -= A[i];
if (lst.find(S) == lst.end()) nxt[i][0] = nax - 1;
else nxt[i][0] = lst[S];
if (i + 1 < N) nxt[i][0] = min(nxt[i][0], nxt[i + 1][0]);
lst[S] = i;
for(int t = 1; t < LG; t++) {
// nxt[i][t] = nxt[nxt[nxt[...nxt[i][t-1]][t-1]][t-1]..]
nxt[i][t] = nxt[i][t-1];
for(int _ = 0; _ < K - 1; _++) nxt[i][t] = nxt[nxt[i][t]][t-1];
}
}
lst.clear();
int Q, l, r, ans; cin >> Q;
while(Q--) {
cin >> l >> r; --l;
ans = 0;
for(int t = LG - 1; t >= 0; t--) {
while(nxt[l][t] <= r) {
ans += pw[t];
l = nxt[l][t];
}
}
cout << ans << nl;
}
exit(0-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... |