Submission #1193745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193745		tkm_algorithms	벽 (IOI14_wall)	C++20	100 / 100	742 ms	48868 KiB

wall

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

//const ll inf = 1e18;

int* res;

struct segtree {
	vector<pair<int, int>> tree;
	void init(int n) {
		int size = 1;
		while (size < n)size <<= 1;
		tree.assign(2*size-1, {0, 0});
	}
	
	void push(int x, int val, int op) {
	int &l = tree[x].first, &r = tree[x].second;
	
		l = (op == 1?max(l, val):min(l, val));
		r = (op == 1?max(r, val):min(r, val));
	}
	
	void apply(int l, int r, int val, int op, int x, int lx, int rx) {
		if (rx <= l || r <= lx)return;
		if (lx >= l && rx <= r) {
			push(x, val, op);
			res[l] = tree[x].first;
			return;
		} 
		
		int &lo = tree[x].first, &hi = tree[x].second;
		push(2*x+1, lo, 1);
		push(2*x+1, hi, 2);
		push(2*x+2, lo, 1);
		push(2*x+2, hi, 2);
		lo = 0, hi = 1e5+5;
		int m = lx+rx>>1;
		apply(l, r, val, op, 2*x+1, lx, m);
		apply(l, r, val, op, 2*x+2, m, rx);
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	segtree a;
	a.init(n);
	res = finalHeight;
	for (int i = 0; i < k; ++i)
		a.apply(left[i], right[i]+1, height[i], op[i], 0, 0, n);
		
	for (int i = 0; i < n; ++i)
		a.apply(i, i+1, 0, 1, 0, 0, n);
}

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