oj.uz

Submission #597225

# Submission time Handle Problem Language Result Execution time Memory
597225 2022-07-15T18:01:48 Z Deepesson Sum Zero (RMI20_sumzero) C++17
100 / 100
 577 ms 18792 KB 
#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;
ll* comprime;
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;
void computa(void){
    respostas_comp=(int*)malloc(MAX*4);
    array=(int*)malloc(MAX*4);
    comprime=(ll*)calloc(MAX*8,1);
    for(int i=0;i!=MAX;++i)respostas_comp[i]=-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;
        respostas_comp[hsh]=i;
    }
    free(respostas_comp);
    free(array);
    free(comprime);
}

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)printf("%d\n",ans[i]);
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1876 KB Output is correct
2 Correct 10 ms 1928 KB Output is correct
3 Correct 7 ms 1876 KB Output is correct
4 Correct 9 ms 1876 KB Output is correct
5 Correct 9 ms 1876 KB Output is correct
6 Correct 7 ms 1876 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1876 KB Output is correct
2 Correct 10 ms 1928 KB Output is correct
3 Correct 7 ms 1876 KB Output is correct
4 Correct 9 ms 1876 KB Output is correct
5 Correct 9 ms 1876 KB Output is correct
6 Correct 7 ms 1876 KB Output is correct
7 Correct 136 ms 3456 KB Output is correct
8 Correct 131 ms 3352 KB Output is correct
9 Correct 131 ms 3392 KB Output is correct
10 Correct 116 ms 3408 KB Output is correct
11 Correct 121 ms 3364 KB Output is correct
12 Correct 132 ms 3468 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1876 KB Output is correct
2 Correct 10 ms 1928 KB Output is correct
3 Correct 7 ms 1876 KB Output is correct
4 Correct 9 ms 1876 KB Output is correct
5 Correct 9 ms 1876 KB Output is correct
6 Correct 7 ms 1876 KB Output is correct
7 Correct 136 ms 3456 KB Output is correct
8 Correct 131 ms 3352 KB Output is correct
9 Correct 131 ms 3392 KB Output is correct
10 Correct 116 ms 3408 KB Output is correct
11 Correct 121 ms 3364 KB Output is correct
12 Correct 132 ms 3468 KB Output is correct
13 Correct 519 ms 11604 KB Output is correct
14 Correct 557 ms 11420 KB Output is correct
15 Correct 572 ms 11856 KB Output is correct
16 Correct 533 ms 11792 KB Output is correct
17 Correct 519 ms 18736 KB Output is correct
18 Correct 577 ms 18792 KB Output is correct