Submission #1193737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193737		tkm_algorithms	Wall (IOI14_wall)	C++20	0 / 100	115 ms	41032 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;
const int N = 4e6+2e5;
struct segtree {
	pair<int, int> tree[N];
	
	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(1, 2*x+1, lo);
		push(2, 2*x+1, hi);
		push(1, 2*x+2, lo);
		push(2, 2*x+2, hi);
		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;
	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: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39