이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 400005;
const int LMAX = 20;
int n, q, a[NMAX], Next[NMAX], jump[NMAX];
long long sp[NMAX];
int L[NMAX], R[NMAX], ANS[NMAX];
void solve()
{
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
sp[i] = sp[i - 1] + a[i];
}
Next[n + 1] = Next[n + 2] = n + 2;
multiset<int64_t> sums{0};
int r = 0;
for(int l = 1; l <= n; ++l) {
while (r <= n) {
if (sums.count(sp[r]) >= 2)
break;
r++;
sums.emplace(sp[r]);
}
Next[l] = r + 1;
sums.erase(sums.find(sp[l - 1]));
}
cin >> q;
for(int i = 1; i <= q; i++)
cin >> L[i] >> R[i];
for(int lg = LMAX; lg >= 0; lg--)
{
for(int i = 1; i <= n + 2; i++)
jump[i] = Next[i];
for(int k = 1; k <= lg; k++)
for(int i = 1; i <= n + 2; i++)
jump[i] = jump[jump[i]];
for(int i = 1; i <= q; i++)
if(jump[L[i]] <= R[i] + 1)
{
ANS[i] += (1 << lg);
L[i] = jump[L[i]];
}
}
for(int i = 1; i <= q; i++)
cout << ANS[i] << '\n';
}
int main()
{
ios_base :: sync_with_stdio(0);
cin.tie(0);
solve();
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... |