Submission #230790

#	Time	Username	Problem	Language	Result	Execution time	Memory
230790		cheissmart	Wall (IOI14_wall)	C++14	100 / 100	742 ms	62224 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(v) (v).beign(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

const int N = 2000006, INF = 1e9 + 7;

struct S {
	int ub, lb;
} t[N * 4];

void init(int v, int tl, int tr) {
	t[v].ub = INF;
	t[v].lb = 0;
	if(tr - tl == 1) return;
	int tm = (tl + tr) / 2;
	init(v*2, tl, tm);
	init(v*2+1, tm, tr);
}

void put_tag(int v, int op, int h) {
	if(op == 1) { // lb
		t[v].lb = max(t[v].lb, h);
		if(t[v].lb >= t[v].ub) t[v].ub = t[v].lb;
	} else { // rb
		t[v].ub = min(t[v].ub, h);
		if(t[v].lb >= t[v].ub) t[v].lb = t[v].ub;
	}
}

void push(int v) {
	put_tag(v*2, 1, t[v].lb);
	put_tag(v*2, 2, t[v].ub);
	put_tag(v*2+1, 1, t[v].lb);
	put_tag(v*2+1, 2, t[v].ub);
	t[v].lb = 0, t[v].ub = INF;
}

void upd(int l, int r, int op, int h, int v, int tl, int tr) {
	if(l >= r) return;
	if(l == tl && r == tr) {
		put_tag(v, op, h);
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	upd(l, min(r, tm), op, h, v*2, tl, tm);
	upd(max(l, tm), r, op, h, v*2+1, tm, tr);
}

void build_ans(int v, int tl, int tr, int* ans) {
	if(tr - tl == 1) {
		ans[tl] = t[v].lb;
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	build_ans(v*2, tl, tm, ans);
	build_ans(v*2 + 1, tm, tr, ans);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	init(1, 0, n);
	for(int i = 0; i < k;i++) {
		upd(left[i], right[i] + 1, op[i], height[i], 1, 0, n);
	}
	build_ans(1, 0, n, finalHeight);
	return;
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39