oj.uz

Submission #1101796

# Submission time Handle Problem Language Result Execution time Memory
1101796 2024-10-16T19:51:07 Z pubin06 Wall (IOI14_wall) C++14
100 / 100
 724 ms 69476 KB 
#include <bits/stdc++.h>
#include "wall.h"
#define fi first
#define se second
using namespace std;

const int MXn = 2e6 + 5, oo = 1e5;

int N;
struct type {
	int LL, RR;
} node[(1 << 22) + 5];
void build(int id = 1, int l = 0, int r = N) {
	if (l == r) {
		node[id] = {0, 0};
		return;
	}
	node[id] = {0, oo};
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
}
void modify(int id, int t, int val) {
	// if (val == 3 && id == 24) cerr << t << ' ' << node[id].LL << ' ' << node[id].RR << '\n';
	if (t == 1) {
		// if (node[id].RR < val) node[id].b = true;
		node[id].LL = max(node[id].LL, val);
		node[id].RR = max(node[id].RR, val);
	} else {
		// if (node[id].LL > val) node[id].b = false;
		node[id].LL = min(node[id].LL, val);
		node[id].RR = min(node[id].RR, val);
	}
	// if (val == 3 && id == 24) cerr << t << ' ' << node[id].LL << ' ' << node[id].RR << '\n';
}
void push(int id) {
	// if (node[id].b) {
		modify(id << 1, 1, node[id].LL);
		modify(id << 1, 2, node[id].RR);
		modify(id << 1 | 1, 1, node[id].LL);
		modify(id << 1 | 1, 2, node[id].RR);
	// } else {
		// modify(id << 1, 2, node[id].LL);
		// modify(id << 1, 1, node[id].RR);
		// modify(id << 1 | 1, 2, node[id].LL);
		// modify(id << 1 | 1, 1, node[id].RR);
	// }
	node[id] = {0, oo};
}
void update(int t, int Lf, int Rt, int val, int id = 1, int l = 0, int r = N) {
	if (Lf <= l && r <= Rt) {
		modify(id, t, val);
		return;
	}
	push(id);
	int mid = (l + r) >> 1;
	if (Lf <= mid) update(t, Lf, Rt, val, id << 1, l, mid);
	if (Rt > mid) update(t, Lf, Rt, val, id << 1 | 1, mid + 1, r);
}
int findh(int i) {
	int id = 1, l = 0, r = N;
	while (l < r) {
		push(id);
		int mid = (l + r) >> 1;
		if (i <= mid) {
			id <<= 1;
			r = mid;
		} else {
			id = id << 1 | 1;
			l = mid + 1;
		}
	}
	return node[id].LL;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	N = n - 1;
	build();
	for (int i = 0; i < k; i++) update(op[i], left[i], right[i], height[i]);
	for (int i = 0; i < n; i++) finalHeight[i] = findh(i);
}

// int main()
// {
  // int n;
  // int k;
// 
  // int i, j;  
  // int status = 0;
// 
  // status = scanf("%d%d", &n, &k);
  // assert(status == 2);
// 
  // int* op = (int*)calloc(sizeof(int), k);
  // int* left = (int*)calloc(sizeof(int), k);
  // int* right = (int*)calloc(sizeof(int), k);
  // int* height = (int*)calloc(sizeof(int), k);
  // int* finalHeight = (int*)calloc(sizeof(int), n);
// 
  // for (i = 0; i < k; i++){
    // status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
    // assert(status == 4);
  // }
// 
  // buildWall(n, k, op, left, right, height, finalHeight);
// 
  // for (j = 0; j < n; j++)
    // printf("%d\n", finalHeight[j]);
//   
  // return 0;
// }

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 83 ms 14084 KB Output is correct
3 Correct 104 ms 9740 KB Output is correct
4 Correct 298 ms 20644 KB Output is correct
5 Correct 193 ms 21580 KB Output is correct
6 Correct 188 ms 20052 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 2900 KB Output is correct
5 Correct 4 ms 2900 KB Output is correct
6 Correct 5 ms 2700 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 87 ms 13900 KB Output is correct
9 Correct 104 ms 9812 KB Output is correct
10 Correct 295 ms 20476 KB Output is correct
11 Correct 209 ms 21544 KB Output is correct
12 Correct 199 ms 20044 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 88 ms 13912 KB Output is correct
15 Correct 19 ms 3668 KB Output is correct
16 Correct 349 ms 20812 KB Output is correct
17 Correct 210 ms 20300 KB Output is correct
18 Correct 184 ms 20304 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 3068 KB Output is correct
5 Correct 5 ms 2900 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 119 ms 13904 KB Output is correct
9 Correct 105 ms 9816 KB Output is correct
10 Correct 297 ms 20568 KB Output is correct
11 Correct 190 ms 21708 KB Output is correct
12 Correct 181 ms 20056 KB Output is correct
13 Correct 1 ms 352 KB Output is correct
14 Correct 86 ms 13920 KB Output is correct
15 Correct 19 ms 3680 KB Output is correct
16 Correct 299 ms 20812 KB Output is correct
17 Correct 190 ms 20300 KB Output is correct
18 Correct 190 ms 20308 KB Output is correct
19 Correct 711 ms 69452 KB Output is correct
20 Correct 717 ms 67148 KB Output is correct
21 Correct 663 ms 69452 KB Output is correct
22 Correct 658 ms 67012 KB Output is correct
23 Correct 668 ms 67156 KB Output is correct
24 Correct 709 ms 67164 KB Output is correct
25 Correct 662 ms 67148 KB Output is correct
26 Correct 656 ms 69476 KB Output is correct
27 Correct 680 ms 69472 KB Output is correct
28 Correct 686 ms 67148 KB Output is correct
29 Correct 675 ms 67164 KB Output is correct
30 Correct 724 ms 67148 KB Output is correct