Submission #467927

#	Time	Username	Problem	Language	Result	Execution time	Memory
467927		MilosMilutinovic	Sum Zero (RMI20_sumzero)	C++14	0 / 100	19 ms	28620 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=400005;
const int L=18;
int a[N];
int st[L][N];
void Build(int n){
    for(int i=0;i<N;i++){
        for(int j=0;j<L;j++)st[j][i]=N-2;
    }
    map<ll,int> was;
    ll sum=0;
    was[0]=0;
    for(int i=1;i<=n;i++){
        sum+=a[i];
        if(was.count(sum)){
            st[0][was[sum]+1]=i;
        }
        was[sum]=i;
    }
    int mn=N-1;
    for(int i=n;i>=1;i--)st[0][i]=min(st[0][i+1],st[0][i]);
    for(int i=1;i<L;i++){
        for(int j=1;j<=n;j++){
            st[i][j]=st[i-1][st[i-1][j]+1];
        }
    }
}
int main(){
    int n;scanf("%i",&n);
    for(int i=1;i<=n;i++)scanf("%i",&a[i]);
    Build(n);
    int q;scanf("%i",&q);
    int l,r,ans=0;
    while(q--){
        scanf("%i%i",&l,&r);
        ans=0;
        for(int i=L-1;i>=0;i--){
            if(st[i][l]<=r)ans+=(1<<i),l=st[i][l]+1;
        }
        printf("%i\n",ans);
    }
    return 0;
}

Compilation message (stderr)

sumzero.cpp: In function 'void Build(int)':
sumzero.cpp:22:9: warning: unused variable 'mn' [-Wunused-variable]
   22 |     int mn=N-1;
      |         ^~
sumzero.cpp: In function 'int main()':
sumzero.cpp:31:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     int n;scanf("%i",&n);
      |           ~~~~~^~~~~~~~~
sumzero.cpp:32:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     for(int i=1;i<=n;i++)scanf("%i",&a[i]);
      |                          ~~~~~^~~~~~~~~~~~
sumzero.cpp:34:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     int q;scanf("%i",&q);
      |           ~~~~~^~~~~~~~~
sumzero.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%i%i",&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 39
• Subtask 3: 0 / 39