이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn = 4e5+3;
const int base = 100;
const int maxlog = 3;
int sparse[maxlog][maxn];
int i,j,p,q,n,m,k,Q,st[3],l,r,a;
unordered_map <long long,int> enc;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n;
st[0] = 1;
st[1] = base;
st[2] = base*base;
p = -1;
sparse[0][0] = -1;
long long sum = 0;
for(i=1; i<=n; i++)
{
cin>>a;
sum = sum+a;
if(enc[sum]!=0 || sum==0)
p = max(p,enc[sum]);
sparse[0][i] = p;
enc[sum] = i;
// cout<<sparse[0][i]<<endl;
}
enc.clear();
for(i=1; i<maxlog; i++)
{
sparse[i][0] = -1;
for(k=1; k<=n; k++)
{
sparse[i][k] = sparse[i-1][k];
for(j=1;sparse[i][k]!=-1 && j<base; j++)
sparse[i][k] = sparse[i-1][sparse[i][k]];
}
}
cin>>Q;
for(i=1; i<=Q; i++)
{
cin>>l>>r;
int ans = 0;
for(j=maxlog-1; j>=0; j--)
{
//cout<<j<<" "<<r<<" "<<sparse[j][r]<<endl;
while(sparse[j][r]>=l-1)
{
ans+=st[j];
r = sparse[j][r];
}
}
cout<<ans<<endl;
}
return 0;
}
/**
10
1 2 -3 0 1 -4 3 2 -1 1
3
1 10
1 5
2 9
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |