oj.uz

Submission #950828

# Submission time Handle Problem Language Result Execution time Memory
950828 2024-03-20T18:53:46 Z venkateskks2304 Sum Zero (RMI20_sumzero) C++14
61 / 100
 203 ms 5728 KB 
// 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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2652 KB Output is correct
2 Correct 11 ms 2652 KB Output is correct
3 Correct 13 ms 2652 KB Output is correct
4 Correct 11 ms 2904 KB Output is correct
5 Correct 13 ms 2652 KB Output is correct
6 Correct 10 ms 2652 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2652 KB Output is correct
2 Correct 11 ms 2652 KB Output is correct
3 Correct 13 ms 2652 KB Output is correct
4 Correct 11 ms 2904 KB Output is correct
5 Correct 13 ms 2652 KB Output is correct
6 Correct 10 ms 2652 KB Output is correct
7 Correct 189 ms 5192 KB Output is correct
8 Correct 203 ms 5728 KB Output is correct
9 Correct 198 ms 4028 KB Output is correct
10 Correct 186 ms 5032 KB Output is correct
11 Correct 197 ms 5036 KB Output is correct
12 Correct 192 ms 4180 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2652 KB Output is correct
2 Correct 11 ms 2652 KB Output is correct
3 Correct 13 ms 2652 KB Output is correct
4 Correct 11 ms 2904 KB Output is correct
5 Correct 13 ms 2652 KB Output is correct
6 Correct 10 ms 2652 KB Output is correct
7 Correct 189 ms 5192 KB Output is correct
8 Correct 203 ms 5728 KB Output is correct
9 Correct 198 ms 4028 KB Output is correct
10 Correct 186 ms 5032 KB Output is correct
11 Correct 197 ms 5036 KB Output is correct
12 Correct 192 ms 4180 KB Output is correct
13 Runtime error 15 ms 5720 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -