# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
928758 |
2024-02-17T04:35:45 Z |
Cutebol |
Wall (IOI14_wall) |
C++17 |
|
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] << ' ' ;
}
//*/
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |