Submission #287218

#	Time	Username	Problem	Language	Result	Execution time	Memory
287218		shivensinha4	Wall (IOI14_wall)	C++17	100 / 100	824 ms	182072 KiB

wall

#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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39