| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 50262 |
2018-06-08T17:13:48 Z |
mirbek01 |
Wall (IOI14_wall) |
C++17 |
|
1304 ms |
89140 KB |
#include "wall.h"
# include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 2;
struct st{
int mn, mx;
st(){
mx = 0;
mn = 1e5 + 1;
}
}t[N * 4];
int n;
void upd(int v, int x, int tp){
if(tp == 1){
t[v].mx = max(t[v].mx, x);
t[v].mn = max(t[v].mn, x);
} else {
t[v].mn = min(t[v].mn, x);
t[v].mx = min(t[v].mx, x);
}
}
void down(int v){
upd(v << 1, t[v].mx, 1);
upd(v << 1, t[v].mn, 2);
upd((v << 1) | 1, t[v].mx, 1);
upd((v << 1) | 1, t[v].mn, 2);
t[v].mx = 0;
t[v].mn = 1e5 + 1;
}
void update(int l, int r, int x, int tp, int v = 1, int tl = 1, int tr = n){
if(l <= tl && tr <= r){
upd(v, x, tp);
return ;
}
if(tl > r || l > tr) return ;
down(v);
int tm = (tl + tr) >> 1;
update(l, r, x, tp, v << 1, tl, tm);
update(l, r, x, tp, (v << 1) | 1, tm + 1, tr);
}
int get(int pos, int v = 1, int tl = 1, int tr = n){
if(tl == tr){
return t[v].mx;
}
down(v);
int tm = (tl + tr) >> 1;
if(pos <= tm)
return get(pos, v << 1, tl, tm);
return get(pos, (v << 1) | 1, tm + 1, tr);
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n = N;
for(int i = 0; i < k; i ++){
update(left[i] + 1, right[i] + 1, height[i], op[i]);
}
for(int i = 0; i < n; i ++){
finalHeight[i] = get(i + 1);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
62968 KB |
Output is correct |
| 2 |
Correct |
69 ms |
63164 KB |
Output is correct |
| 3 |
Correct |
51 ms |
63164 KB |
Output is correct |
| 4 |
Correct |
61 ms |
63164 KB |
Output is correct |
| 5 |
Correct |
51 ms |
63164 KB |
Output is correct |
| 6 |
Correct |
52 ms |
63196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
63196 KB |
Output is correct |
| 2 |
Correct |
230 ms |
70968 KB |
Output is correct |
| 3 |
Correct |
260 ms |
70968 KB |
Output is correct |
| 4 |
Correct |
709 ms |
71540 KB |
Output is correct |
| 5 |
Correct |
425 ms |
72116 KB |
Output is correct |
| 6 |
Correct |
426 ms |
72116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
72116 KB |
Output is correct |
| 2 |
Correct |
49 ms |
72116 KB |
Output is correct |
| 3 |
Correct |
54 ms |
72116 KB |
Output is correct |
| 4 |
Correct |
54 ms |
72116 KB |
Output is correct |
| 5 |
Correct |
54 ms |
72116 KB |
Output is correct |
| 6 |
Correct |
57 ms |
72116 KB |
Output is correct |
| 7 |
Correct |
50 ms |
72116 KB |
Output is correct |
| 8 |
Correct |
241 ms |
72116 KB |
Output is correct |
| 9 |
Correct |
298 ms |
72116 KB |
Output is correct |
| 10 |
Correct |
684 ms |
72116 KB |
Output is correct |
| 11 |
Correct |
437 ms |
72196 KB |
Output is correct |
| 12 |
Correct |
391 ms |
72212 KB |
Output is correct |
| 13 |
Correct |
49 ms |
72212 KB |
Output is correct |
| 14 |
Correct |
223 ms |
72212 KB |
Output is correct |
| 15 |
Correct |
86 ms |
72212 KB |
Output is correct |
| 16 |
Correct |
712 ms |
72212 KB |
Output is correct |
| 17 |
Correct |
409 ms |
72212 KB |
Output is correct |
| 18 |
Correct |
403 ms |
72212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
72212 KB |
Output is correct |
| 2 |
Correct |
50 ms |
72212 KB |
Output is correct |
| 3 |
Correct |
55 ms |
72212 KB |
Output is correct |
| 4 |
Correct |
73 ms |
72212 KB |
Output is correct |
| 5 |
Correct |
65 ms |
72212 KB |
Output is correct |
| 6 |
Correct |
54 ms |
72212 KB |
Output is correct |
| 7 |
Correct |
55 ms |
72212 KB |
Output is correct |
| 8 |
Correct |
214 ms |
72212 KB |
Output is correct |
| 9 |
Correct |
256 ms |
72212 KB |
Output is correct |
| 10 |
Correct |
751 ms |
72212 KB |
Output is correct |
| 11 |
Correct |
581 ms |
72212 KB |
Output is correct |
| 12 |
Correct |
448 ms |
72232 KB |
Output is correct |
| 13 |
Correct |
48 ms |
72232 KB |
Output is correct |
| 14 |
Correct |
245 ms |
72232 KB |
Output is correct |
| 15 |
Correct |
82 ms |
72232 KB |
Output is correct |
| 16 |
Correct |
689 ms |
72232 KB |
Output is correct |
| 17 |
Correct |
500 ms |
72232 KB |
Output is correct |
| 18 |
Correct |
412 ms |
72232 KB |
Output is correct |
| 19 |
Correct |
1289 ms |
89088 KB |
Output is correct |
| 20 |
Correct |
1239 ms |
89088 KB |
Output is correct |
| 21 |
Correct |
1148 ms |
89088 KB |
Output is correct |
| 22 |
Correct |
1075 ms |
89088 KB |
Output is correct |
| 23 |
Correct |
1134 ms |
89088 KB |
Output is correct |
| 24 |
Correct |
1201 ms |
89088 KB |
Output is correct |
| 25 |
Correct |
1264 ms |
89088 KB |
Output is correct |
| 26 |
Correct |
1304 ms |
89088 KB |
Output is correct |
| 27 |
Correct |
1227 ms |
89140 KB |
Output is correct |
| 28 |
Correct |
1201 ms |
89140 KB |
Output is correct |
| 29 |
Correct |
1216 ms |
89140 KB |
Output is correct |
| 30 |
Correct |
1177 ms |
89140 KB |
Output is correct |
