제출 #597192

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
597192		Deepesson	Sum Zero (RMI20_sumzero)	C++17	22 / 100	117 ms	21132 KiB

sumzero

#include <bits/stdc++.h>
#define MAX 405000

using ll = long long;

ll array[MAX];

int N;
ll jump[MAX][20];

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!=20;++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 i=19;i!=-1;--i){
            if(pos>=0&&jump[pos][i]>=l){
              //  std::cout<<"Pular "<<jump[pos][i]<<" "<<l<<" "<<i<<"\n";
                dist+=1<<i;
                pos=jump[pos][i];
            }
        }
        std::cout<<dist<<"\n";
    }
}

• Subtask 1: 22 / 22
• Subtask 2: 0 / 39
• Subtask 3: 0 / 39