제출 #1064491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1064491		Nonoze	Wall (IOI14_wall)	C++17	100 / 100	865 ms	167256 KiB

wall

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