oj.uz

Submission #287214

# Submission time Handle Problem Language Result Execution time Memory
287214 2020-08-31T13:51:53 Z shivensinha4 Wall (IOI14_wall) C++17
100 / 100
 841 ms 183800 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

struct Node {
	ll max, min;
};

class SegmentTree {
	private:
		vector<Node> tree; vector<ll> raw; int n;
		vector<bool> marked;
		
		Node bound = {(ll) 1e6, 0};
		Node resolve(Node p, Node c) {
			if (p.min >= c.max) return {p.min, p.min};
			if (p.max <= c.min) return {p.max, p.max};
			return {min(p.max, c.max), max(p.min, c.min)};
		}
		
		void push(int p) {
			marked[p] = false;
			int c1 = 2*p+1, c2 = 2*p+2;
			marked[c1] = marked[c2] = true;
			tree[c1] = resolve(tree[p], tree[c1]);
			tree[c2] = resolve(tree[p], tree[c2]);
			tree[p] = bound;
		}
		
		// t: 0 -> increase to val, 1 -> decrease to val
		void update(int i, int j, ll k, int t, int l, int r, int p) {
			if (l > j or r < i) return;
			
			if (l >= i and r <= j) {
				marked[p] = true;
				if (t == 0) tree[p] = {max(tree[p].max, k), max(tree[p].min, k)};
				else tree[p] = {min(tree[p].max, k), min(tree[p].min, k)};
				return;
			}
			
			int mid = (l + r) / 2;
			if (marked[p]) push(p);
			int c1 = 2*p+1, c2 = 2*p+2;
			update(i, j, k, t, l, mid, c1); update(i, j, k, t, mid+1, r, c2);
		}
	
	public: 
		SegmentTree(vector<ll> input) {
			raw = input;
			n = raw.size();
			marked.resize(4*n);
			tree.resize(4*n, bound);
		}
		
		void update(int i, int j, int val, int t) {
			update(i, j, val, t, 0, n-1, 0);
		}
		
		void answer(int l, int r, int p, int ans[]) {
			if (l == r) {
				ans[l] = raw[l];
				//if (l == 0) cout << tree[p].max << " " << tree[p].min << endl;
				if (raw[l] > tree[p].max) ans[l] = tree[p].max;
				if (raw[l] < tree[p].min) ans[l] = tree[p].min;
				return;
			}
			
			int mid = (l + r) / 2;
			if (marked[p]) push(p);
			int c1 = 2*p+1, c2 = 2*p+2;
			answer(l, mid, c1, ans); answer(mid+1, r, c2, ans);
		}
};


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  vector<ll> nums(n);
  SegmentTree tree(nums);
  for_(i, 0, k) tree.update(left[i], right[i], height[i], op[i]-1);
  tree.answer(0, n-1, 0, finalHeight);
}


//int main() {
	//#ifndef ONLINE_JUDGE
	//freopen("test.in", "r", stdin);
	//#endif
	
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	
	//int n = 10, k = 6;
	//int op[] = {1, 2, 2, 1, 1, 2};
	//int left[] = {1, 4, 3, 0, 2, 6};
	//int right[] = {8, 9, 6, 5, 2, 7};
	//int height[] = {4, 1, 5, 3, 5, 0};
	//int* finalHeight = (int*)calloc(sizeof(int), n);
	
	//buildWall(10, k, op, left, right, height, finalHeight);
	//for_(i, 0, n) cout << finalHeight[i] << " ";
	//cout << endl;

	//return 0;
//}

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 8 ms 1408 KB Output is correct
5 Correct 5 ms 1408 KB Output is correct
6 Correct 5 ms 1408 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 180 ms 10360 KB Output is correct
3 Correct 207 ms 7288 KB Output is correct
4 Correct 645 ms 18936 KB Output is correct
5 Correct 288 ms 19048 KB Output is correct
6 Correct 286 ms 18936 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 11 ms 1408 KB Output is correct
5 Correct 6 ms 1408 KB Output is correct
6 Correct 7 ms 1408 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 185 ms 10364 KB Output is correct
9 Correct 211 ms 6904 KB Output is correct
10 Correct 698 ms 18936 KB Output is correct
11 Correct 301 ms 19448 KB Output is correct
12 Correct 309 ms 19704 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 180 ms 11140 KB Output is correct
15 Correct 42 ms 2816 KB Output is correct
16 Correct 828 ms 19748 KB Output is correct
17 Correct 298 ms 19716 KB Output is correct
18 Correct 323 ms 19704 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 10 ms 1408 KB Output is correct
5 Correct 6 ms 1408 KB Output is correct
6 Correct 5 ms 1408 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 175 ms 11128 KB Output is correct
9 Correct 214 ms 7420 KB Output is correct
10 Correct 654 ms 19832 KB Output is correct
11 Correct 290 ms 19832 KB Output is correct
12 Correct 276 ms 19704 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 176 ms 11128 KB Output is correct
15 Correct 40 ms 2816 KB Output is correct
16 Correct 759 ms 19320 KB Output is correct
17 Correct 283 ms 18936 KB Output is correct
18 Correct 293 ms 19064 KB Output is correct
19 Correct 759 ms 183548 KB Output is correct
20 Correct 771 ms 183800 KB Output is correct
21 Correct 780 ms 183772 KB Output is correct
22 Correct 778 ms 183676 KB Output is correct
23 Correct 760 ms 183800 KB Output is correct
24 Correct 773 ms 183544 KB Output is correct
25 Correct 841 ms 183288 KB Output is correct
26 Correct 774 ms 183336 KB Output is correct
27 Correct 764 ms 183288 KB Output is correct
28 Correct 766 ms 183288 KB Output is correct
29 Correct 753 ms 182868 KB Output is correct
30 Correct 762 ms 182520 KB Output is correct