oj.uz

Submission #928268

# Submission time Handle Problem Language Result Execution time Memory
928268 2024-02-16T06:33:47 Z Cutebol Wall (IOI14_wall) C++17
24 / 100
 267 ms 23308 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 2 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 102 ms 8236 KB Output is correct
3 Correct 95 ms 4176 KB Output is correct
4 Correct 267 ms 12624 KB Output is correct
5 Correct 208 ms 23308 KB Output is correct
6 Correct 174 ms 21532 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -