Submission #928268

#	Time	Username	Problem	Language	Result	Execution time	Memory
928268		Cutebol	Wall (IOI14_wall)	C++17	24 / 100	267 ms	23308 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std ;
const int N = 2e6 + 5 ;
const int inf = 1e9 ;

template <class T>
bool chmax( T& x , const T& y ){
  bool f = 0 ;
  if ( x < y ) x = y , f = 1 ;
  return f ;
}
template <class T>
bool chmin( T &x , const T &y ){
  bool f = 0 ;
  if ( x > y ) x = y , f = 1 ;
  return f ;
}

int g[N*4] , a[N] ;

void add ( int l , int r  , int h , int tl , int tr , int v ){
	if ( tl > r || tr < l ) return ;
	if ( tl >= l && tr <= r ){
		chmax ( g[v] , h ) ;
		return ;
	} int mid = ( tl + tr ) / 2 ;
	add ( l , r , h , tl , mid , v+v ) ;
	add( l , r , h , mid+1 , tr , v+v+1 ) ;
}

void rem ( int l , int r , int h , int tl , int tr , int v ){
	if ( tl > r || tr < l ) return ;
	if ( tl >= l && tr <= r ){
		chmin ( g[v] , h ) ;
		return ;
	} int mid = ( tl + tr ) / 2 ;
	rem ( l , r , h , tl , mid , v+v ) ;
	rem ( l , r , h , mid+1 , tr , v+v+1 ) ;
}
int get ( int v , int l , int r , int i ){
	if ( i < l || i > r ) return 0 ;
	if ( i == l && l == r ) return g[v] ;
	int mid = ( l + r ) / 2 ;
	return max ({ get( v + v , l , mid , i ) , get ( v + v + 1 , mid+1 , r , i ) , g[v] }) ;
}

int dec ( int v , int l , int r , int i ){
	if ( i < l || i > r ) return inf ;
	if ( i == l && l == r ) return g[v] ;
	int mid = ( l + r ) / 2 ;
	return min ({ dec( v + v , l , mid , i ) , dec ( v + v + 1 , mid+1 , r , i ) , g[v] }) ;
}


void buildWall(int n, int k, int t[], int l[], int r[], int h[], int ans[] ){
	for ( int i = 0 ; i < k ; i ++ ) l[i] ++ , r[i] ++ ;
	int i = 0 ;
	for ( ; i < k ; i ++ ){
		if ( t[i] == 2 ) break ;
		add( l[i] , r[i] , h[i] , 1 , n , 1 ) ;
	}
	for ( int i = 1 ; i <= n ; i ++ ) a[i] = get( 1 , 1 , n , i ) ;
	for ( int i = 1 ; i <= 4*n ; i ++ ) g[i] = inf ;
	for ( ; i < k ; i ++ ) rem( l[i] , r[i] , h[i] , 1 , n , 1 ) ;
	for ( int i = 1 ; i <= n ; i ++ ) chmin ( a[i] , dec( 1 , 1 , n , i ) ) ;
	for ( int i = 0 ; i < n ; i ++ ) ans[i] = a[i+1] ;
}
/*
int n , k , t[N] , l[N] , r[N] , h[N] , ans[N] ;
signed main(){
	cin >> n >> k ;
	for ( int i = 0 ; i < k ; i ++ ) cin >> t[i] >> l[i] >> r[i] >> h[i] ;
	buildWall( n , k , t , l , r , h , ans ) ;
	for ( int i = 0 ; i < n ; i ++ ) cout << ans[i] << ' ' ;
}
//*/

• Subtask 1: 0 / 8
• Subtask 2: 24 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39