oj.uz

Submission #1064491

# Submission time Handle Problem Language Result Execution time Memory
1064491 2024-08-18T13:19:47 Z Nonoze Wall (IOI14_wall) C++17
100 / 100
 865 ms 167256 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) (int)x.size()
#define fi first
#define se second
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)

vector<int> ans;

struct SegTree {
	int n;
	vector<pair<pair<int, int>, pair<int, int>>> tree;
	SegTree(int _n) {n=_n, tree.resize(4*n, {{-1, -1}, {-1, -1}});}

	void add(int node, int h, int op) {
		if (op==0) {
			if (tree[node].fi.se==-1) tree[node].fi={h, op};
			else if (tree[node].fi.se==op) cmax(tree[node].fi.fi, h);
			else if (tree[node].se.se==-1) tree[node].se={h, op}, swap(tree[node].fi, tree[node].se);
			else {
				swap(tree[node].fi, tree[node].se);
				tree[node].fi.fi=max(min(tree[node].se.fi, tree[node].fi.fi), h);
			}
		} else {
			if (tree[node].fi.se==-1) tree[node].fi={h, op};
			else if (tree[node].fi.se==op) cmin(tree[node].fi.fi, h);
			else if (tree[node].se.se==-1) tree[node].se={h, op}, swap(tree[node].fi, tree[node].se);
			else {
				swap(tree[node].fi, tree[node].se);
				tree[node].fi.fi=min(max(tree[node].se.fi, tree[node].fi.fi), h);
			}
		}
	}

	void propagate(int node, int l, int r) { if (l==r || tree[node].fi.se==-1) return;
		if (tree[node].se.se!=-1) {
			add(node*2, tree[node].se.fi, tree[node].se.se);
			add(node*2+1, tree[node].se.fi, tree[node].se.se);
			tree[node].se={-1, -1};
		}
		add(node*2, tree[node].fi.fi, tree[node].fi.se);
		add(node*2+1, tree[node].fi.fi, tree[node].fi.se);
		tree[node].fi={-1, -1};
		return;
	}

	void update(int node, int l, int r, int ql, int qr, int h, bool op) {
		propagate(node, l, r);
		if (l>qr || r<ql) return;
		if (ql<=l && r<=qr) {
			add(node, h, op);
			return;
		}
		int mid=(l+r)/2;
		update(node*2, l, mid, ql, qr, h, op);
		update(node*2+1, mid+1, r, ql, qr, h, op);
	}

	vector<int> ans;
	void query(int node, int l, int r) {
		propagate(node, l, r);
		if (l==r) {
			if (tree[node].fi.se==-1) {
				ans[l]=0;
				return;
			}
			int res=0;
			if (tree[node].fi.se==0) res=tree[node].fi.fi;
			else if (tree[node].se.se!=-1) res=min(tree[node].se.fi, tree[node].fi.fi);
			ans[l]=res;
			return;
		}
		int mid=(l+r)/2;
		query(node*2, l, mid);
		query(node*2+1, mid+1, r);
	}

	vector<int> calc() {
		ans.resize(n);
		query(1, 0, n-1);
		return ans;
	}
};



void buildWall(int n, int k, int ops[], int left[], int right[], int height[], int finalHeight[]) {
	SegTree st(n);
	for (int i=0; i<k; i++) st.update(1, 0, n-1, left[i], right[i], height[i], ops[i]-1);
	vector<int> ans=st.calc();
	for (int i=0; i<n; i++) finalHeight[i]=ans[i];
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 8 ms 1276 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 82 ms 13904 KB Output is correct
3 Correct 213 ms 8784 KB Output is correct
4 Correct 554 ms 25192 KB Output is correct
5 Correct 201 ms 25812 KB Output is correct
6 Correct 213 ms 24320 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 7 ms 1116 KB Output is correct
5 Correct 4 ms 1112 KB Output is correct
6 Correct 4 ms 1148 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 128 ms 13884 KB Output is correct
9 Correct 175 ms 8664 KB Output is correct
10 Correct 568 ms 25156 KB Output is correct
11 Correct 228 ms 25684 KB Output is correct
12 Correct 201 ms 24140 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 82 ms 13908 KB Output is correct
15 Correct 40 ms 2644 KB Output is correct
16 Correct 865 ms 25156 KB Output is correct
17 Correct 266 ms 24656 KB Output is correct
18 Correct 265 ms 24548 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 8 ms 1116 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct
6 Correct 3 ms 1116 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 115 ms 14052 KB Output is correct
9 Correct 244 ms 8944 KB Output is correct
10 Correct 563 ms 25152 KB Output is correct
11 Correct 190 ms 25868 KB Output is correct
12 Correct 195 ms 24148 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 107 ms 14016 KB Output is correct
15 Correct 47 ms 2572 KB Output is correct
16 Correct 857 ms 25168 KB Output is correct
17 Correct 252 ms 24484 KB Output is correct
18 Correct 214 ms 24656 KB Output is correct
19 Correct 583 ms 167248 KB Output is correct
20 Correct 590 ms 167248 KB Output is correct
21 Correct 558 ms 167200 KB Output is correct
22 Correct 493 ms 167252 KB Output is correct
23 Correct 510 ms 167256 KB Output is correct
24 Correct 505 ms 167252 KB Output is correct
25 Correct 492 ms 167252 KB Output is correct
26 Correct 526 ms 167248 KB Output is correct
27 Correct 519 ms 167236 KB Output is correct
28 Correct 504 ms 167252 KB Output is correct
29 Correct 575 ms 167252 KB Output is correct
30 Correct 516 ms 167248 KB Output is correct