Submission #950828

#	Time	Username	Problem	Language	Result	Execution time	Memory
950828		venkateskks2304	Sum Zero (RMI20_sumzero)	C++14	61 / 100	203 ms	5728 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 = 1e5 + 3  ; 
const int K =  18 ;
int arr[N] ; 
int zeros[N] ; 
int par[N] ;
int lift[N] ;  
int ans[N] ;
pii req[N];
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] = par[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] ; 
                   ans[i] += (1<<ll) ; 
              }
     } 

}

unordered_map<ll , int> sums ; 

int main() { 
    // const int N = (int) 2e5 +5  ;
    cin>>n ; 

    memset(zeros,-1,sizeof(zeros));
    memset(ans,0,sizeof(ans));
    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 ; 

    
    memset(par,-1,sizeof(par));
    
    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));

    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<<ans[i]<<endl ; 
    }


} 

Compilation message (stderr)

sumzero.cpp: In function 'void solve(int)':
sumzero.cpp:53:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |               auto &[l,r] = req[i] ;
      |                     ^

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