Submission #132076

#	Time	Username	Problem	Language	Result	Execution time	Memory
132076		Sorting	Wall (IOI14_wall)	C++14	100 / 100	1572 ms	99480 KiB

wall

#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 7;
const int inf = 1e9;

struct node{
	int mn, mx;

	node(){
		mx = 0;
		mn  = inf;
	};
	node(int _mn, int _mx){
		mn = _mn;
		mx = _mx;
	}

	friend void unite(node &prev, node after){
		prev.mn = min(prev.mn, after.mn);
		prev.mx = max(prev.mx, after.mx);

		if(prev.mx > prev.mn){
			if(after.mx == prev.mx){
				prev.mn = prev.mx;
			}
			else{
				prev.mx = prev.mn;
			}
		}
	}
};

node st[4 * N];

void update(int idx, int l, int r, int sl, int sr, node val){
	if(l != r){
		unite(st[2 * idx], st[idx]);
		unite(st[2 * idx + 1], st[idx]);
		st[idx] = node();
	}

	if(l > sr || r < sl){
		return;
	}
	if(sl <= l && r <= sr){
		unite(st[idx], val);

		return;
	}

	int mid = (l + r) / 2;

	update(2 * idx, l, mid, sl, sr, val);
	update(2 * idx + 1, mid + 1, r, sl, sr, val);
}

int query(int idx, int l, int r, int s){
	if(l != r){
		unite(st[2 * idx], st[idx]);
		unite(st[2 * idx + 1], st[idx]);
		st[idx] = node();
	}

	if(l > s || r < s){
		return node().mx;
	}
	if(l == r && l == s){
		return st[idx].mx;
	}

	int mid = (l + r) >> 1;

	int lvalue = query(2 * idx, l, mid, s);
	int rvalue = query(2 * idx + 1, mid + 1, r, s);

	return max(lvalue, rvalue);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i = 0; i < k; i++){
		node t;

		if(op[i] == 1){
			t = node(inf, height[i]);
		}
		else{
			t = node(height[i], 0);
		}

		update(1, 0, n - 1, left[i], right[i], t);
	}

	for(int i = 0; i < n; i++){
		finalHeight[i] = query(1, 0, n - 1, i); 
	}
}

/*int n, k, op2[N], left2[N], right2[N], height2[N], finalHeight2[N];

int main(){
	cin >> n >> k;

	for(int i = 0; i < k; i++){
		cin >> op2[i] >> left2[i] >> right2[i] >> height2[i];
	}

	buildWall(n, k, op2, left2, right2, height2, finalHeight2);

	for(int i = 0; i < n; i++){
		cout << finalHeight2[i] << " ";
	}
	cout << "\n";
	
	return 0;
}*/

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