oj.uz

Submission #287217

# Submission time Handle Problem Language Result Execution time Memory
287217 2020-08-31T13:55:35 Z shivensinha4 Wall (IOI14_wall) C++17
100 / 100
 993 ms 181496 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 merge(Node a, Node b) {
			return {max(a.max, b.max), min(a.min, b.min)};
		}
		
		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 (t == 0 and tree[p].min >= k) return;
			else if (t == 1 and tree[p].max <= k) 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);
			tree[p] = merge(tree[c1], tree[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 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 7 ms 1408 KB Output is correct
5 Correct 7 ms 1408 KB Output is correct
6 Correct 6 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 8740 KB Output is correct
3 Correct 104 ms 5624 KB Output is correct
4 Correct 240 ms 17272 KB Output is correct
5 Correct 243 ms 17272 KB Output is correct
6 Correct 251 ms 17272 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 7 ms 1408 KB Output is correct
5 Correct 6 ms 1408 KB Output is correct
6 Correct 8 ms 1408 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 182 ms 8696 KB Output is correct
9 Correct 101 ms 5620 KB Output is correct
10 Correct 265 ms 17272 KB Output is correct
11 Correct 232 ms 16760 KB Output is correct
12 Correct 253 ms 16888 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 184 ms 8184 KB Output is correct
15 Correct 35 ms 2304 KB Output is correct
16 Correct 598 ms 16888 KB Output is correct
17 Correct 385 ms 16760 KB Output is correct
18 Correct 388 ms 16760 KB Output is correct

Subtask #4
39.0 / 39.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 7 ms 1280 KB Output is correct
5 Correct 6 ms 1280 KB Output is correct
6 Correct 6 ms 1280 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 179 ms 8124 KB Output is correct
9 Correct 102 ms 5368 KB Output is correct
10 Correct 249 ms 16888 KB Output is correct
11 Correct 232 ms 16800 KB Output is correct
12 Correct 263 ms 16760 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 184 ms 8096 KB Output is correct
15 Correct 34 ms 2304 KB Output is correct
16 Correct 591 ms 16888 KB Output is correct
17 Correct 377 ms 16760 KB Output is correct
18 Correct 373 ms 16760 KB Output is correct
19 Correct 981 ms 181368 KB Output is correct
20 Correct 982 ms 181368 KB Output is correct
21 Correct 990 ms 181308 KB Output is correct
22 Correct 969 ms 181368 KB Output is correct
23 Correct 988 ms 181368 KB Output is correct
24 Correct 981 ms 181496 KB Output is correct
25 Correct 981 ms 181368 KB Output is correct
26 Correct 987 ms 181496 KB Output is correct
27 Correct 993 ms 181368 KB Output is correct
28 Correct 974 ms 181368 KB Output is correct
29 Correct 979 ms 181496 KB Output is correct
30 Correct 979 ms 181496 KB Output is correct