#include <bits/stdc++.h>
using namespace std;
const int nx=4e5+5, kx=19;
#define ll long long
int n, q, a[nx], L, R, vl[nx], dp[nx];
map<ll, int> mp;
ll qs;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n;
for (int i=1; i<=n;i ++) cin>>a[i];
mp[0]=1;
for (int i=1; i<=n; i++)
{
qs+=a[i];
if (mp.find(qs)!=mp.end()) vl[i]=mp[qs];
mp[qs]=i+1;
}
for (int i=1; i<=n; i++) vl[i]=max(vl[i], vl[i-1]);
for (int i=1; i<=n; i++) if (vl[i]) dp[i]=dp[vl[i]-1]+1;
cin>>q;
while (q--)
{
cin>>L>>R;
if (dp[R]==0) cout<<0<<'\n';
else
{
int l=L, r=R;
while (l<r)
{
int md=(l+r)/2;
if (vl[md]<l) l=md+1;
else r=md;
}
cout<<dp[R]-dp[l]+1<<'\n';
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4700 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4700 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4700 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |