oj.uz

Submission #520078

# Submission time Handle Problem Language Result Execution time Memory
520078 2022-01-28T09:50:41 Z akhan42 Wall (IOI14_wall) C++17
100 / 100
 1227 ms 89096 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }


struct Seg {
	int n;
	vi mx, mn;
	const int INF = 1000 * 1000;

	Seg(int n): n(n) {
		mx.assign(4 * n, -INF);
		mn.assign(4 * n, INF);

		build();
	}

	void build(int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;

		if(tl == tr) {
			mn[v] = mx[v] = 0;
			return;
		}
		int tm = (tl + tr) / 2;

		build(2 * v, tl, tm);
		build(2 * v + 1, tm + 1, tr);
	}

	void prop_ch(int v, int vc) {
		if(mn[vc] < mx[v])
			mn[vc] = mx[vc] = mx[v];
		else if(mx[vc] > mn[v])
			mn[vc] = mx[vc] = mn[v];
		else {
			maxeq(mx[vc], mx[v]);
			mineq(mn[vc], mn[v]);
		}
	}

	void propagate(int v, int tl, int tr) {
		if(tl == tr)
			return;

		prop_ch(v, 2 * v);
		prop_ch(v, 2 * v + 1);
		mn[v] = INF;
		mx[v] = -INF;
	}

	void update(int l, int r, int ph, int h, int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;
		propagate(v, tl, tr);
		if(l > r)
			return;

		if(tl == l && r == tr) {
//			cout << l << ' ' << r << '\n';
			if(tl == tr) {
				if((ph == 1 && mn[v] < h) || (ph == 2 && mx[v] > h))
					mn[v] = mx[v] = h;
			} else {
				if(ph == 1)
					mx[v] = h;
				else
					mn[v] = h;
			}
			return;
		}
		int tm = (tl + tr) / 2;

		update(l, min(r, tm), ph, h, 2 * v, tl, tm);
		update(max(l, tm + 1), r, ph, h, 2 * v + 1, tm + 1, tr);
	}

	int at(int p, int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;
		propagate(v, tl, tr);

		if(tl == tr) {
			return mn[v];
		}
		int tm = (tl + tr) / 2;

		if(p <= tm)
			return at(p, 2 * v, tl, tm);
		else
			return at(p, 2 * v + 1, tm + 1, tr);
	}
};


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	Seg seg(n);

	forn(i, k) {
		seg.update(left[i], right[i], op[i], height[i]);
	}

	forn(i, n)
		finalHeight[i] = seg.at(i);
}


void solve() {
	int n, k;
	cin >> n >> k;

	int op[k], left[k], right[k], height[k], finalHeight[k];
	forn(i, k)
		cin >> op[i] >> left[i] >> right[i] >> height[i];

	buildWall(n, k, op, left, right, height, finalHeight);
	forn(i, n)
		cout << finalHeight[i] << ' ';
	cout << endl;
}

//
//int main() {
//	ios_base::sync_with_stdio(false);
//	cin.tie(nullptr);
////	cout.tie(nullptr);
//
////	freopen("optmilk.in", "r", stdin);
////	freopen("optmilk.out", "w", stdout);
//
//	int t = 1;
////	cin >> t;
//	while(t--) {
//		solve();
//	}
//}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 8 ms 716 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 7 ms 828 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 138 ms 13844 KB Output is correct
3 Correct 204 ms 7912 KB Output is correct
4 Correct 497 ms 21440 KB Output is correct
5 Correct 344 ms 21812 KB Output is correct
6 Correct 320 ms 20148 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 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 8 ms 820 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 6 ms 812 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 152 ms 13856 KB Output is correct
9 Correct 174 ms 8004 KB Output is correct
10 Correct 512 ms 21244 KB Output is correct
11 Correct 323 ms 21792 KB Output is correct
12 Correct 322 ms 20232 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 131 ms 13888 KB Output is correct
15 Correct 38 ms 1892 KB Output is correct
16 Correct 651 ms 21156 KB Output is correct
17 Correct 341 ms 20640 KB Output is correct
18 Correct 342 ms 20612 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 296 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 716 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 6 ms 716 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 130 ms 13904 KB Output is correct
9 Correct 177 ms 7956 KB Output is correct
10 Correct 501 ms 21128 KB Output is correct
11 Correct 333 ms 21908 KB Output is correct
12 Correct 332 ms 20136 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 131 ms 13892 KB Output is correct
15 Correct 39 ms 1892 KB Output is correct
16 Correct 723 ms 21240 KB Output is correct
17 Correct 330 ms 20656 KB Output is correct
18 Correct 391 ms 20672 KB Output is correct
19 Correct 1185 ms 88952 KB Output is correct
20 Correct 1066 ms 88940 KB Output is correct
21 Correct 1111 ms 88996 KB Output is correct
22 Correct 1052 ms 88988 KB Output is correct
23 Correct 1086 ms 89096 KB Output is correct
24 Correct 1172 ms 88816 KB Output is correct
25 Correct 1227 ms 89004 KB Output is correct
26 Correct 1162 ms 88916 KB Output is correct
27 Correct 1164 ms 88900 KB Output is correct
28 Correct 1161 ms 88960 KB Output is correct
29 Correct 1181 ms 88992 KB Output is correct
30 Correct 1141 ms 88972 KB Output is correct