| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 597206 | Deepesson | Sum Zero (RMI20_sumzero) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define MAX 405000
#define LOG 19
using ll = long long;
int array[MAX];
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 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,int> 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]);
}
pulo_origem[i]=prev;
mapa[s]=i;
}
mapa.clear();
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]<<"\n";
}