제출 #597200

#제출 시각아이디문제언어결과실행 시간메모리
597200DeepessonSum Zero (RMI20_sumzero)C++17
61 / 100
543 ms39112 KiB
#include <bits/stdc++.h> #define MAX 405000 #define LOG 16 using ll = long long; int array[MAX]; int N; int jump[MAX][LOG]; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); std::cin>>N; for(int i=0;i!=N;++i)std::cin>>array[i]; std::map<ll,ll> mapa; mapa[0]=-1; ll prev=-7; ll s=0; for(int i=0;i!=N;++i){ s+=array[i]; ll falta = s; if(mapa.find(falta)!=mapa.end()){ prev=std::max(prev,mapa[falta]); } // std::cout<<s<<"\n"; jump[i][0]=prev; mapa[s]=i; } for(int i=0;i!=N;++i){ // std::cout<<jump[i][0]<<" \n"[i==N-1]; } for(int j=1;j!=LOG;++j){ for(int i=0;i!=N;++i){ int x = jump[i][j-1]; if(x<0)jump[i][j]=x-1; else jump[i][j]=jump[x][j-1]; // std::cout<<jump[i][j]<<" \n"[i==N-1]; } } // std::cout<<"show\n"; int Q; std::cin>>Q; for(int i=0;i!=Q;++i){ int l,r; std::cin>>l>>r;l-=2;--r; int pos = r; ll dist=0; for(int u=0;u!=8;++u){ for(int i=LOG-1;i!=-1;--i){ if(pos>=0&&jump[pos][i]>=l){ dist+=1<<i; pos=jump[pos][i]; } } } std::cout<<dist<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...