oj.uz

Submission #660148

# Submission time Handle Problem Language Result Execution time Memory
660148 2022-11-20T13:53:51 Z Trisanu_Das Wall (IOI14_wall) C++17
100 / 100
 563 ms 99348 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define N 2000010
pair<int, int> seg[4 * N];
 
void update(int s, int e, int i, int l, int r, int cur, bool op){
	cur = max(cur, seg[i].first); cur = min(cur, seg[i].second);
	if(l > e || r < s) return;
	if(l >= s && r <= e){if(!op) seg[i].first = cur; else seg[i].second = cur; return;}
	update(s, e, i * 2, l, (l + r) / 2, cur, op);
	update(s, e, i * 2 + 1, (l + r) / 2 + 1, r, cur, op);
}
 
void make(int l, int r, int i, int cur, int *ans){
	cur = max(cur, seg[i].first); cur = min(cur, seg[i].second);
	if(l == r){ans[l] = cur; return;}
	make(l, (l + r) / 2, i * 2, cur, ans);
	make((l + r) / 2 + 1, r, i * 2 + 1, cur, ans);
}
 
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]){
	for(int i = 1;i <= 4 * n; i++) seg[i] = make_pair(0, INT_MAX);
	for(int i = k - 1; i >= 0; i--)	update(l[i], r[i], 1, 0, n - 1, h[i], op[i] - 1);
	make(0,n - 1, 1, 0, ans);
  	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 4 ms 852 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 154 ms 8092 KB Output is correct
3 Correct 134 ms 4216 KB Output is correct
4 Correct 312 ms 21412 KB Output is correct
5 Correct 243 ms 22596 KB Output is correct
6 Correct 221 ms 20904 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 764 KB Output is correct
5 Correct 4 ms 940 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 141 ms 13896 KB Output is correct
9 Correct 117 ms 7980 KB Output is correct
10 Correct 327 ms 21628 KB Output is correct
11 Correct 239 ms 22536 KB Output is correct
12 Correct 244 ms 20976 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 150 ms 13900 KB Output is correct
15 Correct 21 ms 1932 KB Output is correct
16 Correct 344 ms 21668 KB Output is correct
17 Correct 220 ms 21088 KB Output is correct
18 Correct 249 ms 21084 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 6 ms 824 KB Output is correct
5 Correct 4 ms 764 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 145 ms 13996 KB Output is correct
9 Correct 140 ms 7968 KB Output is correct
10 Correct 332 ms 21428 KB Output is correct
11 Correct 235 ms 22476 KB Output is correct
12 Correct 238 ms 21048 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 150 ms 13956 KB Output is correct
15 Correct 24 ms 2024 KB Output is correct
16 Correct 369 ms 21660 KB Output is correct
17 Correct 225 ms 21216 KB Output is correct
18 Correct 232 ms 21136 KB Output is correct
19 Correct 563 ms 99328 KB Output is correct
20 Correct 543 ms 96808 KB Output is correct
21 Correct 517 ms 99348 KB Output is correct
22 Correct 509 ms 96740 KB Output is correct
23 Correct 515 ms 96892 KB Output is correct
24 Correct 536 ms 96864 KB Output is correct
25 Correct 519 ms 96740 KB Output is correct
26 Correct 516 ms 99248 KB Output is correct
27 Correct 522 ms 99256 KB Output is correct
28 Correct 516 ms 96756 KB Output is correct
29 Correct 532 ms 96724 KB Output is correct
30 Correct 537 ms 96828 KB Output is correct