oj.uz

Submission #492606

# Submission time Handle Problem Language Result Execution time Memory
492606 2021-12-08T06:08:26 Z fhvirus Wall (IOI14_wall) C++17
100 / 100
 943 ms 57696 KB 
#include "wall.h"

#include <algorithm>
#include <vector>
using namespace std;

const int INF = 1e9 + 7;

[[ gnu::pure ]] int id(int l, int r) { return (l + r) | (l != r); }
struct SGT {
	int n; vector<int> mnv, mxv;
	SGT (int nn) : n(nn), mnv(nn * 2, INF), mxv(nn * 2, 0) {}
	void chmax(int u, int v) {
		mnv[u] = max(mnv[u], v);
		mxv[u] = max(mxv[u], v);
	}
	void chmin(int u, int v) {
		mnv[u] = min(mnv[u], v);
		mxv[u] = min(mxv[u], v);
	}
	void push(int i, int l, int r) {
		int m = (l + r) / 2;
		chmax(id(l, m), mxv[i]);
		chmin(id(l, m), mnv[i]);
		chmax(id(m+1, r), mxv[i]);
		chmin(id(m+1, r), mnv[i]);
		mxv[i] = 0;
		mnv[i] = INF;
	}
	void chmax(int l, int r, int ql, int qr, int v) {
		int i = id(l, r);
		if (ql <= l and r <= qr) {
			chmax(i, v);
			return;
		}
		push(i, l, r);
		int m = (l + r) / 2;
		if (ql <= m) chmax(l, m, ql, qr, v);
		if (m < qr) chmax(m+1, r, ql, qr, v);
		return;
	}
	void chmin(int l, int r, int ql, int qr, int v) {
		int i = id(l, r);
		if (ql <= l and r <= qr) {
			chmin(i, v);
			return;
		}
		push(i, l, r);
		int m = (l + r) / 2;
		if (ql <= m) chmin(l, m, ql, qr, v);
		if (m < qr) chmin(m+1, r, ql, qr, v);
		return;
	}
	void leaf(int l, int r, int ans[]) {
		int i = id(l, r);
		if (l == r) {
			ans[l] = min(mnv[i], mxv[i]);
			return;
		}
		push(i, l, r);
		int m = (l + r) / 2;
		leaf(l, m, ans);
		leaf(m+1, r, ans);
		return;
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	SGT sgt(n);
	for (int i = 0; i < k; ++i) {
		if (op[i] == 1)
			sgt.chmax(0, n-1, left[i], right[i], height[i]);
		else
			sgt.chmin(0, n-1, left[i], right[i], height[i]);
	}
	sgt.leaf(0, n-1, finalHeight);
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 416 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 604 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 7 ms 588 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 177 ms 13848 KB Output is correct
3 Correct 211 ms 7648 KB Output is correct
4 Correct 576 ms 19668 KB Output is correct
5 Correct 432 ms 20216 KB Output is correct
6 Correct 419 ms 18652 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 416 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 6 ms 668 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 6 ms 588 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 163 ms 13928 KB Output is correct
9 Correct 240 ms 7664 KB Output is correct
10 Correct 662 ms 19668 KB Output is correct
11 Correct 439 ms 20216 KB Output is correct
12 Correct 427 ms 18756 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 184 ms 13864 KB Output is correct
15 Correct 43 ms 1564 KB Output is correct
16 Correct 518 ms 19672 KB Output is correct
17 Correct 386 ms 19140 KB Output is correct
18 Correct 400 ms 19012 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 6 ms 588 KB Output is correct
5 Correct 6 ms 636 KB Output is correct
6 Correct 6 ms 588 KB Output is correct
7 Correct 0 ms 276 KB Output is correct
8 Correct 150 ms 13960 KB Output is correct
9 Correct 224 ms 7656 KB Output is correct
10 Correct 587 ms 19668 KB Output is correct
11 Correct 414 ms 20224 KB Output is correct
12 Correct 370 ms 18652 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 154 ms 13892 KB Output is correct
15 Correct 37 ms 1624 KB Output is correct
16 Correct 597 ms 19676 KB Output is correct
17 Correct 367 ms 19140 KB Output is correct
18 Correct 427 ms 19096 KB Output is correct
19 Correct 864 ms 57664 KB Output is correct
20 Correct 887 ms 57568 KB Output is correct
21 Correct 932 ms 57696 KB Output is correct
22 Correct 943 ms 57624 KB Output is correct
23 Correct 924 ms 57576 KB Output is correct
24 Correct 871 ms 57660 KB Output is correct
25 Correct 875 ms 57668 KB Output is correct
26 Correct 914 ms 57672 KB Output is correct
27 Correct 898 ms 57676 KB Output is correct
28 Correct 908 ms 57636 KB Output is correct
29 Correct 873 ms 57680 KB Output is correct
30 Correct 897 ms 57664 KB Output is correct