제출 #1080528

#제출 시각아이디문제언어결과실행 시간메모리
1080528batsukh2006Sum Zero (RMI20_sumzero)C++17
61 / 100
516 ms20752 KiB
#include<iostream> #include<map> #include<set> #include<cmath> #include<queue> #include<deque> #include<stack> #include<string> #include<math.h> #include<vector> #include<stdio.h> #include<utility> #include<iomanip> #include<string.h> #include<limits.h> #include<algorithm> #include<functional> #include<unordered_map> using namespace std; #pragma GCC target("popcnt") #define MOD 1000000007 // #define int long long #define ss second #define ff first #define endl '\n' const int mxN=4e5+3; int a[mxN],p[mxN][3]; void solve(){ int n; cin>>n; for(int i=1; i<=n; i++) cin>>a[i]; long sum=0; map<long,int> mp; mp[0]=n+1; p[n+1][0]=n+2; p[n+2][0]=n+2; for(int i=n; i>=1; i--){ sum+=a[i]; if(i==n){ if(mp.find(sum)==mp.end()) p[i][0]=n+2; else p[i][0]=mp[sum]; }else{ if(mp.find(sum)==mp.end()) p[i][0]=p[i+1][0]; else p[i][0]=min(mp[sum],p[i+1][0]); } mp[sum]=i; } for(int i=1; i<3; i++){ for(int j=1; j<=n+2; j++){ p[j][i]=j; for(int k=1; k<=50; k++){ p[j][i]=p[p[j][i]][i-1]; } } } int dp[3]; dp[0]=1; for(int i=1; i<3; i++) dp[i]=dp[i-1]*50; int q; cin>>q; while(q--){ int l,r; cin>>l>>r; int ans=0; for(int i=2; i>=0; i--){ while(p[l][i]-1<=r){ l=p[l][i]; ans+=dp[i]; } } cout<<ans<<endl; } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T=1; // cin>>T; while(T--){ solve(); cout<<endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...