제출 #1080441

#제출 시각아이디문제언어결과실행 시간메모리
1080441batsukh2006Sum Zero (RMI20_sumzero)C++17
0 / 100
2 ms856 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 ss second #define ff first #define endl '\n' void solve(){ int n; cin>>n; vector<int> a(n+1); for(int i=1; i<=n; i++) cin>>a[i]; vector<vector<int> > p(n+3,vector<int>(9)); int sum=0; map<int,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[sum]==0) p[i][0]=n+2; else p[i][0]=mp[sum]; }else{ if(mp[sum]==0) 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<9; i++){ for(int j=1; j<=n+2; j++){ p[j][i]=j; for(int k=1; k<=4; k++){ p[j][i]=p[p[j][i]][i-1]; } } } vector<int> dp(9); dp[0]=1; for(int i=1; i<10; i++) dp[i]=dp[i-1]*4; int q; cin>>q; while(q--){ int l,r; cin>>l>>r; int ans=0; // for(int i=8; i>=0; i--){ // while(p[l][i]-1<=r){ // l=p[l][i]; // ans+=dp[i]; // } // } cout<<ans<<endl; } } signed 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...