Submission #597201

#	Time	Username	Problem	Language	Result	Execution time	Memory
597201		Deepesson	Sum Zero (RMI20_sumzero)	C++17	61 / 100	1088 ms	28852 KiB

sumzero

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

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!=20;++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";
    }
}

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