oj.uz

Submission #950840

# Submission time Handle Problem Language Result Execution time Memory
950840 2024-03-20T19:15:41 Z venkateskks2304 Sum Zero (RMI20_sumzero) C++17
100 / 100
 815 ms 19324 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, 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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5976 KB Output is correct
2 Correct 11 ms 5980 KB Output is correct
3 Correct 12 ms 5980 KB Output is correct
4 Correct 10 ms 6176 KB Output is correct
5 Correct 10 ms 5980 KB Output is correct
6 Correct 10 ms 6220 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5976 KB Output is correct
2 Correct 11 ms 5980 KB Output is correct
3 Correct 12 ms 5980 KB Output is correct
4 Correct 10 ms 6176 KB Output is correct
5 Correct 10 ms 5980 KB Output is correct
6 Correct 10 ms 6220 KB Output is correct
7 Correct 181 ms 10152 KB Output is correct
8 Correct 193 ms 10736 KB Output is correct
9 Correct 214 ms 9324 KB Output is correct
10 Correct 178 ms 10108 KB Output is correct
11 Correct 181 ms 9900 KB Output is correct
12 Correct 185 ms 9296 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5976 KB Output is correct
2 Correct 11 ms 5980 KB Output is correct
3 Correct 12 ms 5980 KB Output is correct
4 Correct 10 ms 6176 KB Output is correct
5 Correct 10 ms 5980 KB Output is correct
6 Correct 10 ms 6220 KB Output is correct
7 Correct 181 ms 10152 KB Output is correct
8 Correct 193 ms 10736 KB Output is correct
9 Correct 214 ms 9324 KB Output is correct
10 Correct 178 ms 10108 KB Output is correct
11 Correct 181 ms 9900 KB Output is correct
12 Correct 185 ms 9296 KB Output is correct
13 Correct 758 ms 16576 KB Output is correct
14 Correct 752 ms 19324 KB Output is correct
15 Correct 762 ms 11352 KB Output is correct
16 Correct 777 ms 19300 KB Output is correct
17 Correct 815 ms 16028 KB Output is correct
18 Correct 785 ms 18120 KB Output is correct