# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1103977 |
2024-10-22T13:52:54 Z |
Naxocist |
Wall (IOI14_wall) |
C++17 |
|
1082 ms |
126004 KB |
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 2e9
const int N = 2e6 + 3;
struct node {
int val, lzmn, lzmx;
node(): val(0), lzmn(INF), lzmx(-INF) {}
} seg[4*N];
int n;
void push(int i, int l, int r) {
seg[i].val = min(seg[i].val, seg[i].lzmn);
seg[i].val = max(seg[i].val, seg[i].lzmx);
int mn = seg[i].lzmn, mx = seg[i].lzmx;
if(l != r) {
seg[2*i].lzmn = min(seg[2*i].lzmn, mn);
seg[2*i+1].lzmn = min(seg[2*i+1].lzmn, mn);
seg[2*i].lzmn = max(seg[2*i].lzmn, mx);
seg[2*i+1].lzmn = max(seg[2*i+1].lzmn, mx);
seg[2*i].lzmx = max(seg[2*i].lzmx, mx);
seg[2*i+1].lzmx = max(seg[2*i+1].lzmx, mx);
seg[2*i].lzmx = min(seg[2*i].lzmx, mn);
seg[2*i+1].lzmx = min(seg[2*i+1].lzmx, mn);
}
seg[i].lzmn = INF, seg[i].lzmx = -INF;
}
void upd(int a, int b, int mn, int mx, int i = 1, int l = 1, int r = n) {
push(i,l,r);
if(a <= l and r <= b) {
seg[i].lzmx = mx;
seg[i].lzmn = mn;
push(i,l,r);
return ;
}
if(r < a or l > b) return ;
int md = l + (r-l)/2;
upd(a,b,mn,mx,2*i,l,md); upd(a,b,mn,mx,2*i+1,md+1,r);
}
int qry(int p, int i = 1, int l = 1, int r = n) {
push(i,l,r);
if(l == r) return seg[i].val;
int md = l + (r-l)/2;
if(p <= md) return qry(p,2*i,l,md);
return qry(p,2*i+1,md+1,r);
}
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) {
int l = left[i], r = right[i], o = op[i], h = height[i]; l++, r++;
int mn, mx;
if(o == 1) upd(l,r,INF,h); // add
else upd(l,r,h,-INF); // rem
}
for(int i=0; i<n; ++i) {
finalHeight[i] = qry(i+1);
}
return;
}
Compilation message
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:61:9: warning: unused variable 'mn' [-Wunused-variable]
61 | int mn, mx;
| ^~
wall.cpp:61:13: warning: unused variable 'mx' [-Wunused-variable]
61 | int mn, mx;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
94164 KB |
Output is correct |
2 |
Correct |
52 ms |
94328 KB |
Output is correct |
3 |
Correct |
48 ms |
94280 KB |
Output is correct |
4 |
Correct |
37 ms |
94280 KB |
Output is correct |
5 |
Correct |
50 ms |
94536 KB |
Output is correct |
6 |
Correct |
32 ms |
94564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
94288 KB |
Output is correct |
2 |
Correct |
113 ms |
101960 KB |
Output is correct |
3 |
Correct |
220 ms |
101264 KB |
Output is correct |
4 |
Correct |
477 ms |
102728 KB |
Output is correct |
5 |
Correct |
311 ms |
108616 KB |
Output is correct |
6 |
Correct |
318 ms |
111180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
94288 KB |
Output is correct |
2 |
Correct |
16 ms |
94428 KB |
Output is correct |
3 |
Correct |
42 ms |
94320 KB |
Output is correct |
4 |
Correct |
32 ms |
94584 KB |
Output is correct |
5 |
Correct |
37 ms |
94432 KB |
Output is correct |
6 |
Correct |
36 ms |
94280 KB |
Output is correct |
7 |
Correct |
25 ms |
94248 KB |
Output is correct |
8 |
Correct |
123 ms |
101960 KB |
Output is correct |
9 |
Correct |
175 ms |
100680 KB |
Output is correct |
10 |
Correct |
540 ms |
102728 KB |
Output is correct |
11 |
Correct |
314 ms |
103228 KB |
Output is correct |
12 |
Correct |
322 ms |
111164 KB |
Output is correct |
13 |
Correct |
26 ms |
94280 KB |
Output is correct |
14 |
Correct |
104 ms |
107336 KB |
Output is correct |
15 |
Correct |
65 ms |
95492 KB |
Output is correct |
16 |
Correct |
542 ms |
102976 KB |
Output is correct |
17 |
Correct |
308 ms |
107760 KB |
Output is correct |
18 |
Correct |
306 ms |
111432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
94288 KB |
Output is correct |
2 |
Correct |
27 ms |
94292 KB |
Output is correct |
3 |
Correct |
24 ms |
94280 KB |
Output is correct |
4 |
Correct |
34 ms |
94544 KB |
Output is correct |
5 |
Correct |
32 ms |
94280 KB |
Output is correct |
6 |
Correct |
34 ms |
94536 KB |
Output is correct |
7 |
Correct |
14 ms |
94336 KB |
Output is correct |
8 |
Correct |
118 ms |
101960 KB |
Output is correct |
9 |
Correct |
223 ms |
101204 KB |
Output is correct |
10 |
Correct |
481 ms |
109896 KB |
Output is correct |
11 |
Correct |
295 ms |
103212 KB |
Output is correct |
12 |
Correct |
280 ms |
103256 KB |
Output is correct |
13 |
Correct |
19 ms |
94384 KB |
Output is correct |
14 |
Correct |
104 ms |
107336 KB |
Output is correct |
15 |
Correct |
41 ms |
95424 KB |
Output is correct |
16 |
Correct |
507 ms |
108100 KB |
Output is correct |
17 |
Correct |
300 ms |
107852 KB |
Output is correct |
18 |
Correct |
301 ms |
102984 KB |
Output is correct |
19 |
Correct |
1074 ms |
120132 KB |
Output is correct |
20 |
Correct |
1069 ms |
117576 KB |
Output is correct |
21 |
Correct |
1082 ms |
125244 KB |
Output is correct |
22 |
Correct |
986 ms |
126004 KB |
Output is correct |
23 |
Correct |
976 ms |
118004 KB |
Output is correct |
24 |
Correct |
1004 ms |
123100 KB |
Output is correct |
25 |
Correct |
1061 ms |
122940 KB |
Output is correct |
26 |
Correct |
1060 ms |
120200 KB |
Output is correct |
27 |
Correct |
1066 ms |
120356 KB |
Output is correct |
28 |
Correct |
1048 ms |
117576 KB |
Output is correct |
29 |
Correct |
999 ms |
117824 KB |
Output is correct |
30 |
Correct |
967 ms |
117832 KB |
Output is correct |