Submission #950840

#	Time	Username	Problem	Language	Result	Execution time	Memory
950840		venkateskks2304	Sum Zero (RMI20_sumzero)	C++17	100 / 100	815 ms	19324 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, zerosector 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 <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
 
#pragma GCC target("avx2,popcnt")
#pragma GCC optimize("O3,unroll-loops")
// #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 = 4e5 + 3  ; 
const int K =  18 ;

int arr[N] ; 
int zeros[N] ;
int lift[N] ;  
pii req[N];
unordered_map<ll , int> sums ; 

int n , q ; 

void solve(int ll) { 
     
    for ( int k = 0 ; k <= ll ; k++ ) {  
        for ( int i = 0 ; i < n ; i++ ) {
           if ( k == 0 ) lift[i] = arr[i] ; 
           else {     
              if ( lift[i] != -1 ) lift[i] = lift[lift[i]] ;
            }
        }
    }

     FOR(i,q) { 
              auto &[l,r] = req[i] ; 
            //   cout<<i<<" "<<l<<" "<<r<<" "<<ll<<endl ;  
              if(l > r || l > n-1) { continue; }
              if ( l == -1 ) break ; 
              if ( lift[l] == -1 ) continue ; 
              if ( lift[l] <= r + 1 ) {
                   l = lift[l] ; 
                   zeros[i] += (1<<ll) ; 
              }
     } 

}

int main() { 
    // const int N = (int) 2e5 +5  ;
    cin>>n ; 
    
    // arr = new int[N] ; 
    // zeros = new int[N] ; 

    memset(zeros,-1,sizeof(zeros));

    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 ; 
    // delete[] arr ; 
    // delete[] zeros ; 

    // arr = new int[N] ; 
    // lift = new int[N] ; 
    // zeros = new int[N] ; 

    memset(arr,-1,sizeof(arr));
    memset(lift,-1,sizeof(lift));
    
    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) ; 
        arr[i] = last_zero  ; 
    }
   
    memset(zeros,0,sizeof(zeros));
    
    // FOR(i,n) cout<<arr[i]<<" " ; 
    // cout<<endl ; 
    

    FOR(i,q) { 
        int l , r ; 
        cin>>l>>r ;
        l-- ; r-- ; 
        req[i] = {l,r} ; 
    }
    
    for(int i = K-1 ;  i >= 0 ; i--) solve(i) ; 

    FOR(i,q) { 
        cout<<zeros[i]<<endl ; 
    }


} 

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