이 제출은 이전 버전의 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];
unordered_map<long long, int> mp;
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;
for(int i = n; i >= 1; i--)
{
Next[i] = Next[i + 1];
mp[sp[i]] = i;
if(mp[sp[i - 1]])
Next[i] = min(Next[i], mp[sp[i - 1]] + 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... |