Submission #956648

#TimeUsernameProblemLanguageResultExecution timeMemory
956648Batorgil952Sum Zero (RMI20_sumzero)C++14
61 / 100
391 ms43880 KiB
#include<bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair using namespace std; const int N=4e5+5; int a[N]; int dp[N][19]; map< ll, int > M; int main(){ int n, i, j, q, l, r, ans; ll s; scanf("%d",&n); for(i=1; i<=n; i++){ scanf("%lld",&a[i]); } s=0; M[0]=0; for(i=1; i<=n; i++){ s+=a[i]; if(M[s]!=0){ dp[i][1]=M[s]+1; } else{ if(s==0) dp[i][1]=1; else dp[i][1]=-1; } if(dp[i][1]==-1 && i>1){ dp[i][1]=dp[i-1][1]; } else if(i>1) dp[i][1]=max(dp[i][1], dp[i-1][1]); M[s]=i; } for(i=1; i<=n; i++){ // cout<<dp[i][1]<<" "; for(j=2; j<=18; j++){ if((dp[i][j-1]-1)>0) dp[i][j]=dp[dp[i][j-1]-1][j-1]; else dp[i][j]=-1; // cout<<dp[i][j]<<" "; } // cout<<endl; } scanf("%d",&q); while(q--){ scanf("%d",&l); scanf("%d",&r); ans=0; for(i=18; i>=1; i--){ if(r>=0){ if(dp[r][i]>=l){ ans+=(1<<(i-1)); r=dp[r][i]; r--; } } } printf("%d\n", ans); } return 0; }

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:20:13: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'int*' [-Wformat=]
   20 |   scanf("%lld",&a[i]);
      |          ~~~^  ~~~~~
      |             |  |
      |             |  int*
      |             long long int*
      |          %d
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("%lld",&a[i]);
      |   ~~~~~^~~~~~~~~~~~~~
sumzero.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
sumzero.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   scanf("%d",&l);
      |   ~~~~~^~~~~~~~~
sumzero.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d",&r);
      |   ~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...