oj.uz

답안 #928758

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
928758 2024-02-17T04:35:45 Z Cutebol 벽 (IOI14_wall) C++17
100 / 100
 822 ms 86224 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 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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2392 KB Output is correct
3 Correct 2 ms 2392 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 5 ms 3016 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 110 ms 15972 KB Output is correct
3 Correct 162 ms 6812 KB Output is correct
4 Correct 440 ms 23528 KB Output is correct
5 Correct 254 ms 24528 KB Output is correct
6 Correct 229 ms 22916 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2504 KB Output is correct
4 Correct 8 ms 2648 KB Output is correct
5 Correct 5 ms 2652 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 113 ms 15924 KB Output is correct
9 Correct 194 ms 9856 KB Output is correct
10 Correct 448 ms 23528 KB Output is correct
11 Correct 266 ms 24564 KB Output is correct
12 Correct 237 ms 23056 KB Output is correct
13 Correct 1 ms 2456 KB Output is correct
14 Correct 135 ms 16024 KB Output is correct
15 Correct 32 ms 3788 KB Output is correct
16 Correct 517 ms 23784 KB Output is correct
17 Correct 257 ms 23040 KB Output is correct
18 Correct 235 ms 23124 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 3 ms 2392 KB Output is correct
3 Correct 2 ms 2392 KB Output is correct
4 Correct 6 ms 2896 KB Output is correct
5 Correct 5 ms 2652 KB Output is correct
6 Correct 5 ms 2836 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 112 ms 15948 KB Output is correct
9 Correct 148 ms 9844 KB Output is correct
10 Correct 416 ms 23780 KB Output is correct
11 Correct 227 ms 24400 KB Output is correct
12 Correct 222 ms 22860 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 119 ms 15944 KB Output is correct
15 Correct 29 ms 3812 KB Output is correct
16 Correct 485 ms 23660 KB Output is correct
17 Correct 247 ms 23212 KB Output is correct
18 Correct 232 ms 23116 KB Output is correct
19 Correct 801 ms 86048 KB Output is correct
20 Correct 773 ms 81364 KB Output is correct
21 Correct 790 ms 86224 KB Output is correct
22 Correct 793 ms 81468 KB Output is correct
23 Correct 796 ms 81452 KB Output is correct
24 Correct 779 ms 81488 KB Output is correct
25 Correct 789 ms 81420 KB Output is correct
26 Correct 785 ms 86092 KB Output is correct
27 Correct 781 ms 86012 KB Output is correct
28 Correct 761 ms 81240 KB Output is correct
29 Correct 822 ms 81656 KB Output is correct
30 Correct 786 ms 81488 KB Output is correct