Submission #928758

#	Time	Username	Problem	Language	Result	Execution time	Memory
928758		Cutebol	Wall (IOI14_wall)	C++17	100 / 100	822 ms	86224 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 mx[N*4] , mn[N*4] , a[N] ;

void push ( int v ){
	chmax( mx[v*2] , mx[v] ) ;
	chmax( mn[v*2] , mx[v] ) ;
	chmin( mx[v*2] , mn[v] ) ;
	chmin( mn[v*2] , mn[v] ) ;
	chmax( mx[v*2+1] , mx[v] ) ;
	chmax( mn[v*2+1] , mx[v] ) ;
	chmin( mx[v*2+1] , mn[v] ) ;
	chmin( mn[v*2+1] , mn[v] ) ;
	mx[v] = 0 , mn[v] = inf ;
}

void upd ( int v , int l , int r , int tl , int tr , int h , int t ){
	if ( l > tr || r < tl ) return ;
	if ( l >= tl && r <= tr ){
		if ( t == 1 ) chmax( mx[v] , h ) , chmax ( mn[v] , h ) ;
		else chmin( mx[v] , h ) , chmin ( mn[v] , h ) ;
		return ;
	} int mid = ( l + r ) / 2 ;
	push(v) ;
	upd ( v + v , l , mid , tl , tr , h , t ) ;
	upd ( v + v + 1 , mid+1 , r , tl , tr , h , t ) ;
}

int get ( int v , int l , int r , int i ){
	if ( l == r ) return mx[v] ;
	push(v) ;
	int m = ( l + r ) / 2 ;
	if ( i <= m ) return get ( v+v , l , m , i ) ;
	else return get ( v+v+1 , m+1 , r , i ) ;
} 

void buildWall(int n, int k, int t[], int l[], int r[], int h[], int ans[] ){
	fill( mn , mn+4*n , inf ) ;
	for ( int i = 0 ; i < k ; i ++ ) l[i] ++ , r[i] ++ ;
	for ( int i = 0 ; i < k ; i ++ ){
		upd ( 1 , 1 , n , l[i] , r[i] , h[i] , t[i] ) ;
	}
	for ( int i = 0 ; i < n ; i ++ ) ans[i] = get( 1 , 1 , n , 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: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39