| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 49574 |
2018-05-31T11:03:25 Z |
khsoo01 |
Wall (IOI14_wall) |
C++11 |
|
1309 ms |
162944 KB |
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int L = (1<<21), inf = 1e9;
struct SEG {
int mn[2*L], mx[2*L];
void init () {
for(int i=2*L;i--;) {
mn[i] = 0;
mx[i] = inf;
}
}
void relax (int P, int O, int V) {
if(O == 1) {
mn[P] = max(mn[P], V);
if(mn[P] > mx[P]) mx[P] = mn[P];
}
else {
mx[P] = min(mx[P], V);
if(mn[P] > mx[P]) mn[P] = mx[P];
}
}
void lazydown (int P) {
relax(2*P, 1, mn[P]);
relax(2*P, 2, mx[P]);
relax(2*P+1, 1, mn[P]);
relax(2*P+1, 2, mx[P]);
mn[P] = 0;
mx[P] = inf;
}
void upd (int S, int E, int O, int V, int SS = 0, int SE = L-1, int P = 1) {
if(S <= SS && SE <= E) {
relax(P, O, V);
return;
}
if(E < SS || SE < S) return;
lazydown(P);
int M = (SS+SE)/2;
upd(S, E, O, V, SS, M, 2*P);
upd(S, E, O, V, M+1, SE, 2*P+1);
}
int get (int I, int SS = 0, int SE = L-1, int P = 1) {
if(SS == SE) return mn[P];
lazydown(P);
int M = (SS+SE)/2;
return I <= M ? get(I, SS, M, 2*P) : get(I, M+1, SE, 2*P+1);
}
} seg;
void buildWall (int N, int K, int O[], int L[], int R[], int H[], int FH[]){
seg.init();
for(int i=0;i<K;i++) {
seg.upd(L[i], R[i], O[i], H[i]);
}
for(int i=0;i<N;i++) {
FH[i] = seg.get(i);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
33144 KB |
Output is correct |
| 2 |
Correct |
32 ms |
33472 KB |
Output is correct |
| 3 |
Correct |
28 ms |
33472 KB |
Output is correct |
| 4 |
Correct |
35 ms |
33568 KB |
Output is correct |
| 5 |
Correct |
34 ms |
33840 KB |
Output is correct |
| 6 |
Correct |
33 ms |
34072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
34072 KB |
Output is correct |
| 2 |
Correct |
455 ms |
47456 KB |
Output is correct |
| 3 |
Correct |
248 ms |
47456 KB |
Output is correct |
| 4 |
Correct |
654 ms |
61508 KB |
Output is correct |
| 5 |
Correct |
551 ms |
72284 KB |
Output is correct |
| 6 |
Correct |
397 ms |
80692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
80692 KB |
Output is correct |
| 2 |
Correct |
35 ms |
80692 KB |
Output is correct |
| 3 |
Correct |
34 ms |
80692 KB |
Output is correct |
| 4 |
Correct |
38 ms |
80692 KB |
Output is correct |
| 5 |
Correct |
41 ms |
80692 KB |
Output is correct |
| 6 |
Correct |
37 ms |
80692 KB |
Output is correct |
| 7 |
Correct |
28 ms |
80692 KB |
Output is correct |
| 8 |
Correct |
521 ms |
85820 KB |
Output is correct |
| 9 |
Correct |
277 ms |
85820 KB |
Output is correct |
| 10 |
Correct |
689 ms |
99856 KB |
Output is correct |
| 11 |
Correct |
411 ms |
110348 KB |
Output is correct |
| 12 |
Correct |
397 ms |
118996 KB |
Output is correct |
| 13 |
Correct |
28 ms |
118996 KB |
Output is correct |
| 14 |
Correct |
455 ms |
124000 KB |
Output is correct |
| 15 |
Correct |
79 ms |
124000 KB |
Output is correct |
| 16 |
Correct |
891 ms |
134856 KB |
Output is correct |
| 17 |
Correct |
386 ms |
143752 KB |
Output is correct |
| 18 |
Correct |
363 ms |
145692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
145692 KB |
Output is correct |
| 2 |
Correct |
44 ms |
145692 KB |
Output is correct |
| 3 |
Correct |
27 ms |
145692 KB |
Output is correct |
| 4 |
Correct |
40 ms |
145692 KB |
Output is correct |
| 5 |
Correct |
36 ms |
145692 KB |
Output is correct |
| 6 |
Correct |
34 ms |
145692 KB |
Output is correct |
| 7 |
Correct |
25 ms |
145692 KB |
Output is correct |
| 8 |
Correct |
454 ms |
145692 KB |
Output is correct |
| 9 |
Correct |
240 ms |
145692 KB |
Output is correct |
| 10 |
Correct |
715 ms |
145692 KB |
Output is correct |
| 11 |
Correct |
390 ms |
146020 KB |
Output is correct |
| 12 |
Correct |
367 ms |
146020 KB |
Output is correct |
| 13 |
Correct |
28 ms |
146020 KB |
Output is correct |
| 14 |
Correct |
563 ms |
146020 KB |
Output is correct |
| 15 |
Correct |
72 ms |
146020 KB |
Output is correct |
| 16 |
Correct |
1185 ms |
146020 KB |
Output is correct |
| 17 |
Correct |
396 ms |
146020 KB |
Output is correct |
| 18 |
Correct |
392 ms |
146020 KB |
Output is correct |
| 19 |
Correct |
1089 ms |
162944 KB |
Output is correct |
| 20 |
Correct |
1016 ms |
162944 KB |
Output is correct |
| 21 |
Correct |
1016 ms |
162944 KB |
Output is correct |
| 22 |
Correct |
1102 ms |
162944 KB |
Output is correct |
| 23 |
Correct |
1209 ms |
162944 KB |
Output is correct |
| 24 |
Correct |
1309 ms |
162944 KB |
Output is correct |
| 25 |
Correct |
1002 ms |
162944 KB |
Output is correct |
| 26 |
Correct |
1002 ms |
162944 KB |
Output is correct |
| 27 |
Correct |
1197 ms |
162944 KB |
Output is correct |
| 28 |
Correct |
1079 ms |
162944 KB |
Output is correct |
| 29 |
Correct |
998 ms |
162944 KB |
Output is correct |
| 30 |
Correct |
1072 ms |
162944 KB |
Output is correct |
