oj.uz

Submission #299146

# Submission time Handle Problem Language Result Execution time Memory
299146 2020-09-14T14:03:43 Z vitkishloh228 Wall (IOI14_wall) C++14
100 / 100
 1287 ms 123772 KB 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int, int>> t;//min,max
vector<int> mod;
void push(int v, int l, int r) {
	if (l == r) mod[v] = -1;
	else {
		if (mod[v] != -1) {
			mod[2 * v] = mod[v];
			mod[2 * v + 1] = mod[v];
			t[2 * v] = { mod[v],mod[v] };
			t[2 * v + 1] = t[2 * v];
			mod[v] = -1;
		}
	}
}
void upd1(int v, int tl, int tr, int l, int r, int x) {//if a[i]< h a[i]=h;
	push(v, tl, tr);
	if (tl > tr || l > r) return;
	if (tl == l && tr == r) {
		if (t[v].first > x) {
			return;
		}
		if (t[v].second <= x) {
			t[v] = { x,x };
			mod[v] = x;
			return;
		}
	}
	int tm = (tl + tr) / 2;
	upd1(2 * v, tl, tm, l, min(r, tm), x);
	upd1(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, x);
	t[v].first = min(t[2 * v].first, t[2 * v + 1].first);
	t[v].second = max(t[2 * v].second, t[2 * v + 1].second);
}
void upd0(int v, int tl, int tr, int l, int r, int x) {//if a[i]>h a[i]=h
	push(v, tl, tr);
	if (tl > tr || l > r) return;
	if (tl == l && tr == r) {
		if (t[v].second < x) {
			return;
		}
		if (t[v].first >= x) {
			t[v] = { x,x };
			mod[v] = x;
			return;
		}
	}
	int tm = (tl + tr) / 2;
	upd0(2 * v, tl, tm, l, min(r, tm), x);
	upd0(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, x);
	t[v].first = min(t[2 * v].first, t[2 * v + 1].first);
	t[v].second = max(t[2 * v].second, t[2 * v + 1].second);
}
int get(int v, int tl, int tr, int pos) {
	push(v, tl, tr);
	if (tl == tr) return t[v].first;
	else {
		int tm = (tl + tr) / 2;
		if (pos <= tm) return get(2 * v, tl, tm, pos);
		else return get(2 * v + 1, tm + 1, tr, pos);
	}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	/*
	int i, mn, mx;
	for (i = 0; i < k; i++) {
		if (op[i] == 1) mn = height[i], mx = 1e9;
		else mn = 0, mx = height[i];
		update(1, 0, n - 1, left[i], right[i], mn, mx);
	}
	for (i = 0; i < n; i++) {
		finalHeight[i] = query(1, 0, n - 1, i);
	}
	*/
	int q = k;
	//cin >> n >> q;
	t.resize(4 * n);
	mod = vector<int>(4 * n, -1);
	for (int i=0;i<q;++i) {
		int tt, l, r, h;
		//cin >> tt >> l >> r >> h;
		tt = op[i];
		l = left[i];
		 r = right[i];
		 h = height[i];
		//--l, --r;
		if (tt == 1) {
			upd1(1, 0, n - 1, l, r, h);
		}
		else {
			upd0(1, 0, n - 1, l, r, h);
		}
	}
	for (int i = 0; i < n; ++i) {
		finalHeight[i] = get(1, 0, n - 1, i);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 7 ms 1024 KB Output is correct
6 Correct 7 ms 1024 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 174 ms 11208 KB Output is correct
3 Correct 212 ms 8408 KB Output is correct
4 Correct 640 ms 17400 KB Output is correct
5 Correct 420 ms 17912 KB Output is correct
6 Correct 401 ms 18168 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 10 ms 1024 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 7 ms 1024 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 169 ms 11128 KB Output is correct
9 Correct 210 ms 8312 KB Output is correct
10 Correct 671 ms 17272 KB Output is correct
11 Correct 408 ms 17272 KB Output is correct
12 Correct 386 ms 18168 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 179 ms 12688 KB Output is correct
15 Correct 48 ms 2296 KB Output is correct
16 Correct 933 ms 17572 KB Output is correct
17 Correct 409 ms 17656 KB Output is correct
18 Correct 406 ms 17656 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 11 ms 1024 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 8 ms 1024 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 175 ms 11256 KB Output is correct
9 Correct 210 ms 8312 KB Output is correct
10 Correct 643 ms 17272 KB Output is correct
11 Correct 409 ms 17248 KB Output is correct
12 Correct 395 ms 18172 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 180 ms 12668 KB Output is correct
15 Correct 63 ms 2296 KB Output is correct
16 Correct 909 ms 17656 KB Output is correct
17 Correct 394 ms 17656 KB Output is correct
18 Correct 404 ms 17656 KB Output is correct
19 Correct 1254 ms 123512 KB Output is correct
20 Correct 1287 ms 121132 KB Output is correct
21 Correct 1250 ms 123660 KB Output is correct
22 Correct 1242 ms 121080 KB Output is correct
23 Correct 1238 ms 121348 KB Output is correct
24 Correct 1237 ms 121080 KB Output is correct
25 Correct 1244 ms 121080 KB Output is correct
26 Correct 1275 ms 123556 KB Output is correct
27 Correct 1272 ms 123772 KB Output is correct
28 Correct 1239 ms 121132 KB Output is correct
29 Correct 1279 ms 120876 KB Output is correct
30 Correct 1256 ms 120956 KB Output is correct