| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 49573 |
2018-05-31T11:01:36 Z |
khsoo01 |
Wall (IOI14_wall) |
C++11 |
|
1420 ms |
262144 KB |
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int L = (1<<21), inf = 1e9;
int n;
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 |
29 ms |
33148 KB |
Output is correct |
| 2 |
Correct |
34 ms |
33512 KB |
Output is correct |
| 3 |
Correct |
34 ms |
33512 KB |
Output is correct |
| 4 |
Correct |
38 ms |
33648 KB |
Output is correct |
| 5 |
Correct |
40 ms |
33752 KB |
Output is correct |
| 6 |
Correct |
36 ms |
33968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
33968 KB |
Output is correct |
| 2 |
Correct |
440 ms |
47740 KB |
Output is correct |
| 3 |
Correct |
246 ms |
47740 KB |
Output is correct |
| 4 |
Correct |
624 ms |
61564 KB |
Output is correct |
| 5 |
Correct |
411 ms |
72336 KB |
Output is correct |
| 6 |
Correct |
439 ms |
80964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
80964 KB |
Output is correct |
| 2 |
Correct |
33 ms |
80964 KB |
Output is correct |
| 3 |
Correct |
32 ms |
80964 KB |
Output is correct |
| 4 |
Correct |
39 ms |
80964 KB |
Output is correct |
| 5 |
Correct |
39 ms |
80964 KB |
Output is correct |
| 6 |
Correct |
36 ms |
80964 KB |
Output is correct |
| 7 |
Correct |
29 ms |
80964 KB |
Output is correct |
| 8 |
Correct |
537 ms |
86112 KB |
Output is correct |
| 9 |
Correct |
242 ms |
86112 KB |
Output is correct |
| 10 |
Correct |
628 ms |
99940 KB |
Output is correct |
| 11 |
Correct |
410 ms |
110728 KB |
Output is correct |
| 12 |
Correct |
442 ms |
119344 KB |
Output is correct |
| 13 |
Correct |
26 ms |
119344 KB |
Output is correct |
| 14 |
Correct |
461 ms |
124176 KB |
Output is correct |
| 15 |
Correct |
76 ms |
124176 KB |
Output is correct |
| 16 |
Correct |
821 ms |
135000 KB |
Output is correct |
| 17 |
Correct |
406 ms |
144092 KB |
Output is correct |
| 18 |
Correct |
404 ms |
153164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
153164 KB |
Output is correct |
| 2 |
Correct |
32 ms |
153164 KB |
Output is correct |
| 3 |
Correct |
30 ms |
153164 KB |
Output is correct |
| 4 |
Correct |
38 ms |
153164 KB |
Output is correct |
| 5 |
Correct |
37 ms |
153164 KB |
Output is correct |
| 6 |
Correct |
36 ms |
153164 KB |
Output is correct |
| 7 |
Correct |
28 ms |
153164 KB |
Output is correct |
| 8 |
Correct |
450 ms |
158604 KB |
Output is correct |
| 9 |
Correct |
277 ms |
158604 KB |
Output is correct |
| 10 |
Correct |
624 ms |
172436 KB |
Output is correct |
| 11 |
Correct |
386 ms |
183080 KB |
Output is correct |
| 12 |
Correct |
391 ms |
191728 KB |
Output is correct |
| 13 |
Correct |
28 ms |
191728 KB |
Output is correct |
| 14 |
Correct |
504 ms |
196540 KB |
Output is correct |
| 15 |
Correct |
75 ms |
196540 KB |
Output is correct |
| 16 |
Correct |
872 ms |
207692 KB |
Output is correct |
| 17 |
Correct |
410 ms |
216664 KB |
Output is correct |
| 18 |
Correct |
388 ms |
225660 KB |
Output is correct |
| 19 |
Correct |
1104 ms |
253240 KB |
Output is correct |
| 20 |
Correct |
1111 ms |
261196 KB |
Output is correct |
| 21 |
Correct |
1097 ms |
262144 KB |
Output is correct |
| 22 |
Correct |
1163 ms |
262144 KB |
Output is correct |
| 23 |
Correct |
1157 ms |
262144 KB |
Output is correct |
| 24 |
Correct |
1232 ms |
262144 KB |
Output is correct |
| 25 |
Correct |
1233 ms |
262144 KB |
Output is correct |
| 26 |
Correct |
1136 ms |
262144 KB |
Output is correct |
| 27 |
Correct |
1420 ms |
262144 KB |
Output is correct |
| 28 |
Correct |
1039 ms |
262144 KB |
Output is correct |
| 29 |
Correct |
996 ms |
262144 KB |
Output is correct |
| 30 |
Correct |
1006 ms |
262144 KB |
Output is correct |
