제출 #597223

#제출 시각아이디문제언어결과실행 시간메모리
597223DeepessonSum Zero (RMI20_sumzero)C++17
61 / 100
995 ms24404 KiB
#include <bits/stdc++.h> #define MAX 405000 #define LOG 19 using ll = long long; int N; int jump[MAX][2]; int pulo_origem[MAX]; void simular_camada(int u){ for(int i=0;i!=N;++i)jump[i][0]=pulo_origem[i]; for(int j=1;j!=u+1;++j){ int cord = j&1; int oposto = !cord; for(int i=0;i!=N;++i){ int x = jump[i][oposto]; if(x<0)jump[i][cord]=x-1; else jump[i][cord]=jump[x][oposto]; } } } int array[MAX]; ll comprime[MAX]; int sz; void work(){ ll s=0; for(int i=0;i!=N;++i){ s+=array[i]; comprime[i+1]=s; } std::sort(comprime,&comprime[N+5]); sz=N+5; } int find(ll x){ int l=0,r=sz-1; while(l<r){ int m = (l+r)/2; if(comprime[m]>=x){ r=m; }else l=m+1; } return l; } int respostas_comp[MAX]; void computa(void){ for(auto&x:respostas_comp)x=-7; for(int i=0;i!=N;++i)std::cin>>array[i]; work(); int prev=-7; respostas_comp[find(0)]=-1; ll s=0; for(int i=0;i!=N;++i){ ll x=array[i]; s+=x; ll hsh=find(s); if(respostas_comp[hsh]!=-7){ prev=std::max(prev,respostas_comp[hsh]); } pulo_origem[i]=prev; // std::cout<<pulo_origem[i]<<" "; respostas_comp[hsh]=i; } // std::cout<<"\n"; } int main() { std::cin>>N; computa(); int Q; std::cin>>Q; int ans[Q]={},pos[Q],lim[Q]; for(int i=0;i!=Q;++i){ int l,r; std::cin>>l>>r;l-=2;--r; pos[i] = r; lim[i] = l; } ///Exponenciacao binaria for(int j=LOG-1;j!=-1;--j){ simular_camada(j); for(int i=0;i!=Q;++i){ if(pos[i]>=0&&jump[pos[i]][j&1]>=lim[i]){ ans[i]+=1<<j; pos[i]=jump[pos[i]][j&1]; } } } for(int i=0;i!=Q;++i)std::cout<<ans[i]<<std::endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...