Submission #950783

#	Time	Username	Problem	Language	Result	Execution time	Memory
950783		venkateskks2304	Sum Zero (RMI20_sumzero)	C++14	61 / 100	218 ms	11968 KiB

sumzero

// good problem 
// given a array and queries (l,r) we need to find the mimimum number of segments to split subarray [l,r] 
// so that each subsegment has hcf as 1 . 
// https://codeforces.com/contest/1516/problem/D
// used array to calculate prime factors of a number 
// didnt construct the tree and directly found the lift 
// as the tree when rooted at n+1 for all where numbers of depth i is less than nodes of depth i-1
// so, ansector of a node if always higher than it . 
// so when constructing lift construct from root (n+1) and decrease to 1 . 


#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef set<pii> sii ;
typedef vector<int> vi ;
typedef multiset<int, greater<int> > msi ;
typedef set<int> si ;
#define FOR(i,b) for (int i=0; i<b; i++)
#define FORB(i,a,b) for (int i=int(a); i<(int)b; i++)
#define FOR3(l,w,h) FOR(i,l) FOR(j,w) FOR(k,h) 
#define FOR2(l,w) FOR(i,l) FOR(j,w) 
#define inf 1e8 + 1  

const int N = (int) 1e5 +5  ;
int arr[N] ; 
int lift[N][20] ; 
int zeros[N] ; 
int par[N] ; 
unordered_map<ll , int> sums ; 
    
int main() { 
    memset(zeros,-1,sizeof(zeros));
    int n , q ; 
    cin>>n ; 
    FOR(i,n) cin>>arr[i] ; 
    cin>>q ; 
    ll sum = 0 ;
    zeros[0] = -1 ; 
    FOR(i,n) { 
        sum += (ll) arr[i] ;
        if ( sums.find(sum) != sums.end() ) { 
             zeros[sums[sum] + 1] = i  ; 
        }
        if ( sum == 0 && zeros[0] == -1 )  zeros[0] = i ; 
        sums[sum] = i ; 
    }

    // FOR(i,n) cout<<zeros[i]<<" " ; 
    // cout<<endl ; 

    int last_zero = -1 ; 
    int n_max = -1 ; 
    
    for(int i = n-1 ; i >= 0 ; i-- ) {  
        if ( last_zero == -1 ) { 
              if ( zeros[i] != -1 ) last_zero = zeros[i] + 1 ; 
        } else { 
              if ( zeros[i] != -1 )
                 last_zero = min(last_zero, zeros[i] + 1) ; 
        }
        if ( last_zero != -1 ) n_max = max(n_max,last_zero) ; 
        par[i] = last_zero  ; 
    }
    
    // FOR(i,n) cout<<par[i]<<" " ; 
    // cout<<endl ; 
    
    memset(lift,-1,sizeof(lift));
    if ( n_max >= 0 ) {  
         FOR (i,20) lift[n_max][i] = -1 ; 
         for ( int i = n_max - 1 ; i >= 0 ; i--  ) { 
               lift[i][0] = par[i] ;
            //    if ( i == 1   ) cout<<endl<<lift[i][0]<<endl ;  
               for ( int j = 1 ; j < 20 ; j++ )  { 
                    if ( lift[i][j-1] == -1 ) lift[i][j] = -1 ; 
                    else lift[i][j] = lift[lift[i][j-1]][j-1] ; 
               }
         }
    }
    
    while ( q-- ) { 
        int l , r ; 
        cin>>l>>r ;
        l-- ; r-- ; 
        int k = 0 ;         
        if(l > r || l > n) { cout << "0\n"; continue; } 
        for ( int i = 19 ; i >= 0 ; i-- ) { 
            //   cout<<lift[l][i]<<" "<<l<<" "<<i<<" "<<r<<endl ; 
              if ( lift[l][i] == -1 ) continue ; 
              if ( lift[l][i] <= r + 1 ) { 
                   l = lift[l][i] ; 
                   k += (1<<i) ; 
              }
        }
        cout<<k<<endl ; 
    }
} 

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