Submission #826046

#	Time	Username	Problem	Language	Result	Execution time	Memory
826046		lollipop	Radio Towers (IOI22_towers)	C++17	11 / 100	4075 ms	225600 KiB

towers

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define ll long long
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 1000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int N = 4e5 + 10 ;
//mt19937 R(time(0));
map < string , int > ma , ma1 ;

#include "towers.h"



int n , a[ N ] ; 

pair < int , int > node[ 4 * N ] ;
void build( int v , int vl , int vr ){
    if( vl == vr ){
        node[ v ] = { a[ vl - 1 ] , vl - 1 } ;
        return ; 
    }
    int vm= ( vl + vr ) / 2 ;
    build( v + v , vl , vm ) ;
    build( v + v + 1 , vm + 1 , vr ) ;
    node[ v ] = max( node[ v + v ] , node[ v + v + 1 ] ) ;
    return ;
}
pair < int , int > get( int v , int vl , int vr , int l , int r ){
    if( l > r ) return { 0 , 0 } ;
    if( vl == l && vr == r ) return node[ v ] ;
    int vm = ( vl + vr ) / 2 ;
    pair < int , int > a , b ;
    a = get( v + v , vl , vm, l , min( r , vm ) ) ;
    b = get( v + v + 1 , vm + 1 , vr , max( vm + 1 , l ) , r ) ;
    return max( a , b ) ; 
}

void init(int N, std::vector<int> H){
    n = N ; FOR( i , N ) a[ i ] = H[ i ] ;
    // if this works make it into segment tree ?
    build( 1 , 1 , n ) ;
    return ;
}


map < pair < int , pair < int , int > > , int > dp ; 
int get( int l , int r , int mx , int d ){
   pair < int , pair < int , int > > axla ;
   axla.f = l ; axla.s.f = r ; axla.s.s = mx ;
   if( dp.find( axla ) != dp.end() ) return dp[ axla ] ; 
   if( l > r ) return 0 ;
   if( l == r && a[ l ] <= mx ) return 1 ;
   if( l == r ) return 0 ;

   pair < int , int > p ;
   p = get( 1 , 1 , n , l + 1 , r + 1 ) ;

   int cur_max = p.f ;
   int cur_pos = p.s ;
   int pas = 0 ;
   // now case work 
   if( cur_max <= mx ) pas = 1 ;
   int A , B ;
   // first both sides 
   A = get( l , cur_pos - 1 , cur_max - d , d ) ;
   B = get( cur_pos + 1 , r , cur_max - d , d ) ;
   pas = max( pas , A + B ) ; 
   // only left side 
   A = get( l , cur_pos - 1 , mx , d ) ;
   pas = max( pas , A ) ; 
   // only right 
   B = get( cur_pos + 1 , r , mx , d ) ; 
   pas = max( pas , B ) ; 
   // Done? Hopefully
   dp[ axla ] = pas ;
   return pas ;
}
int max_towers(int L, int R, int D){
   pair < int , int > p ;
   p = get( 1 , 1 , n , L + 1 , R + 1 ) ;
   int mx = p.f ;
   int pos = p.s ;
   return max( 1 , ( get( L , pos - 1 , mx , D ) + get( pos + 1 , R , mx - D , D ) ) ) ;
}


// int main() {
//   int N, Q;
//   assert(2 == scanf("%d %d", &N, &Q));
//   std::vector<int> H(N);
//   for (int i = 0; i < N; ++i) {
//     assert(1 == scanf("%d", &H[i]));
//   }
//   init(N, H);

//   for (int i = 0; i < Q; ++i) {
//     int L, R, D;
//     assert(3 == scanf("%d %d %d", &L, &R, &D));
//     printf("%d\n", max_towers(L, R, D));
//   }
//   return 0;
// }

• Subtask 1: 0 / 4
• Subtask 2: 11 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23