제출 #1097933

#제출 시각아이디문제언어결과실행 시간메모리
1097933LM1Sum Zero (RMI20_sumzero)C++14
61 / 100
250 ms24776 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],ans[N],p1[N],p2[N]; 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; unordered_map<int,int>sf; sf[0]=n+1; nxt[n+1]=n+2; nxt[n+2]=n+2; for(int i=n;i>=1;i--){ sum+=a[i]; if(sf[sum]==0)nxt[i]=nxt[i+1]; else nxt[i]=min(sf[sum],nxt[i+1]); sf[sum]=i; } // for(int i=1;i<=n;i++){ // cout<<nxt[i]<<" "; // }cout<<'\n'; int Q;cin>>Q; pii q[Q]; for(int i=0;i<Q;i++){ cin>>q[i].ff>>q[i].ss; } for(int jump=18;jump>=0;jump--){ for(int i=1;i<=n+2;i++){ p1[i]=p2[i]=nxt[i]; } for(int j=1;j<=jump;j++){ for(int i=1;i<=n+2;i++){ swap(p1[i],p2[i]); } for(int i=1;i<=n+2;i++){ p1[i]=p2[p2[i]]; /* p[i][j]=p[p[i][j-1][j-1] p[i][j]=p1[i] p[i][j-1]=p2[i] p1[i]=p2[p2[i]] */ } } for(int i=0;i<Q;i++){ if(p1[q[i].ff]<=q[i].ss+1){ ans[i]+=(1<<jump); q[i].ff=p1[q[i].ff]; } } } for(int i=0;i<Q;i++)cout<<ans[i]<<"\n"; } /* 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...