Submission #1097918

#TimeUsernameProblemLanguageResultExecution timeMemory
1097918LM1Sum Zero (RMI20_sumzero)C++14
0 / 100
3 ms856 KiB
#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> //#define int long long #define pb push_back #define vi vector<int> #define ff first #define ss second using namespace std; const int N=4e5+5; int nxt[N]; int solve(int l,int r){ int ans=0; while(nxt[l]<=r+1){ ans++; l=nxt[l]; } return ans; } int main(){ ios_base::sync_with_stdio(NULL);cin.tie(NULL); int n;cin>>n; int a[n+1]; for(int i=1;i<=n;i++)cin>>a[i]; int sum=0; map<int,int>sf; sf[0]=n+1; nxt[n+1]=n+10; for(int i=n;i>=1;i--){ sum+=a[i]; if(sf[sum]==0)nxt[i]=nxt[i+1]; else nxt[i]=sf[sum]; sf[sum]=i; } int Q;cin>>Q; pii q[Q]; for(int i=0;i<Q;i++){ cin>>q[i].ff>>q[i].ss; cout<<solve(q[i].ff,q[i].ss)<<"\n"; } // for(int jump=18;jump>=0;jump--){ // // } } /* dp[i]=dp[i-1] pr[i] ind=mp[pr[i]] dp[i]=max(dp[i],dp[ind-1]+1) mp[pr[i]]=i nxt i, j i<=k<=j pr[k,j]=0 l,r ans=0; while(l<=r){ ans++; l=nxt[l]; } p[i][0]=nxt[i] for(int j=1;j<19;j++){ for(int i=0;i<n;i++){ // i ze xar // 2^j cali next p[i][j]=p[p[i][j-1][j-1] } } l,r for(int j=18;j>=0;j--){ if(p[l][j]<=r){ l=p[l][j] ans+=(1<<j) } } p[i][j]=p[p[i][j-1][j-1]; x=p[i][j-1] p[x][j-1] nxt[i] */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...