oj.uz

Submission #287218

# Submission time Handle Problem Language Result Execution time Memory
287218 2020-08-31T13:56:52 Z shivensinha4 Wall (IOI14_wall) C++17
100 / 100
 824 ms 182072 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#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 3 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 8 ms 1280 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 5 ms 1280 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 172 ms 8184 KB Output is correct
3 Correct 207 ms 5240 KB Output is correct
4 Correct 641 ms 16760 KB Output is correct
5 Correct 305 ms 16884 KB Output is correct
6 Correct 292 ms 16764 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 8 ms 1280 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 173 ms 8184 KB Output is correct
9 Correct 208 ms 5240 KB Output is correct
10 Correct 659 ms 16860 KB Output is correct
11 Correct 296 ms 16760 KB Output is correct
12 Correct 289 ms 16864 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 176 ms 8184 KB Output is correct
15 Correct 40 ms 2304 KB Output is correct
16 Correct 754 ms 16760 KB Output is correct
17 Correct 293 ms 16936 KB Output is correct
18 Correct 291 ms 16888 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 404 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 8 ms 1280 KB Output is correct
5 Correct 5 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 176 ms 8184 KB Output is correct
9 Correct 208 ms 5240 KB Output is correct
10 Correct 674 ms 16860 KB Output is correct
11 Correct 302 ms 16760 KB Output is correct
12 Correct 285 ms 16888 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 175 ms 8184 KB Output is correct
15 Correct 40 ms 2300 KB Output is correct
16 Correct 755 ms 17016 KB Output is correct
17 Correct 290 ms 16888 KB Output is correct
18 Correct 285 ms 16760 KB Output is correct
19 Correct 786 ms 181480 KB Output is correct
20 Correct 780 ms 181368 KB Output is correct
21 Correct 790 ms 181372 KB Output is correct
22 Correct 795 ms 181880 KB Output is correct
23 Correct 824 ms 181908 KB Output is correct
24 Correct 776 ms 181900 KB Output is correct
25 Correct 771 ms 181868 KB Output is correct
26 Correct 783 ms 182020 KB Output is correct
27 Correct 779 ms 182008 KB Output is correct
28 Correct 775 ms 181880 KB Output is correct
29 Correct 777 ms 182072 KB Output is correct
30 Correct 768 ms 181880 KB Output is correct