#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
int n,nn=0,pr[400069][5];
pair<long long,int> a[400069];
int main()
{
int t,rr,i,j,k,l,sz,z;
long long sm=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&k);
sm+=k;
a[i]={sm,i};
}
a[n+1]={0,0};
sort(a+1,a+n+2);
for(i=1;i<=n;i++)
{
if(a[i].fr==a[i+1].fr)
{
nn++;
a[nn]={a[i].sc+1,a[i+1].sc};
}
}
sort(a+1,a+nn+1);
sz=nn;
nn=0;
for(i=1;i<=sz;i++)
{
for(;nn&&a[nn].sc>=a[i].sc;nn--);
nn++;
a[nn]=a[i];
}
a[nn+1]={n+1,n+1};
for(i=0;i<5;i++)
{
pr[nn+1][i]=nn+1;
}
for(i=nn;i;i--)
{
pr[i][0]=upper_bound(a+1,a+nn+1,mp((long long)a[i].sc,n+1))-a;
for(j=1;j<5;j++)
{
pr[i][j]=pr[pr[pr[pr[pr[pr[pr[pr[i][j-1]][j-1]][j-1]][j-1]][j-1]][j-1]][j-1]][j-1];
}
}
scanf("%d",&t);
for(rr=0;rr<t;rr++)
{
scanf("%d%d",&k,&l);
k=lower_bound(a+1,a+nn+1,mp((long long)k,0))-a;
z=0;
if(a[k].sc<=l)
{
z++;
for(i=4;i+1;i--)
{
for(;a[pr[k][i]].sc<=l;k=pr[k][i])
{
z+=1<<i*3;
}
}
}
printf("%d\n",z);
}
}
Compilation message
sumzero.cpp: In function 'int main()':
sumzero.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
sumzero.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | scanf("%d",&k);
| ~~~~~^~~~~~~~~
sumzero.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d",&t);
| ~~~~~^~~~~~~~~
sumzero.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d%d",&k,&l);
| ~~~~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
332 KB |
Output is correct |
2 |
Correct |
5 ms |
332 KB |
Output is correct |
3 |
Correct |
4 ms |
332 KB |
Output is correct |
4 |
Correct |
5 ms |
332 KB |
Output is correct |
5 |
Correct |
4 ms |
332 KB |
Output is correct |
6 |
Correct |
4 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
332 KB |
Output is correct |
2 |
Correct |
5 ms |
332 KB |
Output is correct |
3 |
Correct |
4 ms |
332 KB |
Output is correct |
4 |
Correct |
5 ms |
332 KB |
Output is correct |
5 |
Correct |
4 ms |
332 KB |
Output is correct |
6 |
Correct |
4 ms |
332 KB |
Output is correct |
7 |
Correct |
102 ms |
2628 KB |
Output is correct |
8 |
Correct |
108 ms |
3128 KB |
Output is correct |
9 |
Correct |
101 ms |
2492 KB |
Output is correct |
10 |
Correct |
106 ms |
2628 KB |
Output is correct |
11 |
Correct |
126 ms |
3152 KB |
Output is correct |
12 |
Correct |
98 ms |
2500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
332 KB |
Output is correct |
2 |
Correct |
5 ms |
332 KB |
Output is correct |
3 |
Correct |
4 ms |
332 KB |
Output is correct |
4 |
Correct |
5 ms |
332 KB |
Output is correct |
5 |
Correct |
4 ms |
332 KB |
Output is correct |
6 |
Correct |
4 ms |
332 KB |
Output is correct |
7 |
Correct |
102 ms |
2628 KB |
Output is correct |
8 |
Correct |
108 ms |
3128 KB |
Output is correct |
9 |
Correct |
101 ms |
2492 KB |
Output is correct |
10 |
Correct |
106 ms |
2628 KB |
Output is correct |
11 |
Correct |
126 ms |
3152 KB |
Output is correct |
12 |
Correct |
98 ms |
2500 KB |
Output is correct |
13 |
Correct |
522 ms |
10304 KB |
Output is correct |
14 |
Correct |
562 ms |
12240 KB |
Output is correct |
15 |
Correct |
529 ms |
9668 KB |
Output is correct |
16 |
Correct |
509 ms |
10076 KB |
Output is correct |
17 |
Correct |
540 ms |
12100 KB |
Output is correct |
18 |
Correct |
508 ms |
16676 KB |
Output is correct |