Submission #488717

#	Time	Username	Problem	Language	Result	Execution time	Memory
488717		grt	Wall (IOI14_wall)	C++17	24 / 100	443 ms	11660 KiB

wall

#include <bits/stdc++.h>
#include <wall.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const int INF = 1e9;
int n, k;

struct Node {
	int h, H;
	void eval(Node &u) {
		h = max(h, u.h);
		if(h > H) H = INF;
		H = min(H, u.H);
		if(h > H) h = H;
	}
};

Node T[(1 << 21)];

void prop(int x) {
	T[2*x].eval(T[x]);
	T[2*x+1].eval(T[x]);
	T[x] = {0, INF};
}

void init(int l, int r, int v) {
	T[v].h = 0; T[v].H = INF;
	if(l == r) return;
	int mid = (l + r)/2;
	init(l,mid,v*2);
	init(mid+1,r,v*2+1);
}

void tree(int l, int r, int v) {
	cout << l << " " << r << ": " << T[v].h << " " << T[v].H << "\n";
	if(l==r) return;
	tree(l,(l+r)/2,v*2);
	tree((l+r)/2+1,r,v*2+1);
}

void upd(int a, int b, int l, int r, int v, Node u) {
	if(a <= l && r <= b) {
		T[v].eval(u);
		return;
	}
	prop(v);
	int mid = (l + r) / 2;
	if(a <= mid) upd(a,b,l,mid,v*2,u);
	if(mid < b) upd(a,b,mid+1,r,v*2+1,u);
}

int res[2'000'000 + 10];

void rec(int l, int r, int v) {
	if(l == r) {
		res[l] = min(T[v].h, T[v].H);
		return;
	}
	prop(v);
	int mid = (l+r)/2;
	rec(l,mid,v*2);
	rec(mid+1,r,v*2+1);
}


void buildWall(int _n, int _k, int op[], int l[], int r[], int hei[], int ans[]) {
	n = _n; k = _k;
	init(0, n-1, 1);
	for(int i = 0; i < k; ++i) {
		if(op[i]-1) {
			upd(l[i], r[i], 0, n-1, 1, {0, hei[i]});
		} else {
			upd(l[i], r[i], 0, n-1, 1, {hei[i], INF});
		}
		//tree(0,n-1,1);
		//cout << "-----\n";
	}
	rec(0,n-1,1);
	//tree(0,n-1,1);
	//cout << "----\n";
	for(int i = 0; i < n; ++i) {
		ans[i] = res[i];
		//cout << ans[i] << " ";
	}
}


//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//cin >> n >> k;
	//int op[k], l[k], r[k], hei[k], ans[n];
	//for(int i = 0; i < k; ++i) {
		//cin >> op[i] >> l[i] >> r[i] >> hei[i];
	//}
	//buildWall(n,k,op,l,r,hei,ans);
//}

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