Submission #538596

#	Time	Username	Problem	Language	Result	Execution time	Memory
538596		Cantfindme	Wall (IOI14_wall)	C++17	61 / 100	851 ms	262144 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long
typedef long long ll;
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()

const int maxn = 2000010;
const ll INF = INT_MAX/4;
const int mod = 1e9+7;

ll ans[maxn];

struct node {
	int s, m, e;
	ll maxv= INF, minv=0;
	node *l, *r;
	node (int _s, int _e) {
		s = _s; e = _e; m = (s+e)/2;
		if (s != e) {
			l = new node(s,m);
			r = new node(m+1,e);
		}
	}

	void calc(int type, ll x) {
		if (type == 0) { //minimise
			maxv = min(maxv, x);
			minv = min(minv, x);
		} else {
			minv = max(minv, x);
			maxv = max(maxv, x);
		}
	}

	void push() {
		if (minv != 0) {
			l -> setmin(s, m, minv);
			r -> setmin(m+1, e, minv);
			minv = 0;
		}

		if (maxv != INF) {
			l -> setmax(s, m, maxv);
			r -> setmax(m+1, e, maxv);
			maxv = INF;
		}
	}

	void setmax(int x, int y, ll nv) {
		if (s == x and e == y) {
			calc(0, nv);
		} else {
			push();
			if (x > m) r -> setmax(x,y, nv);
			else if (y <= m) l -> setmax(x,y,nv);
			else l -> setmax(x,m,nv), r -> setmax(m+1,y,nv);
		}
	}

	void setmin(int x, int y, ll nv) {
		if (s == x and e == y) {
			calc(1, nv);
		} else {
			push();
			if (x > m) r -> setmin(x,y, nv);
			else if (y <= m) l -> setmin(x,y,nv);
			else l -> setmin(x,m,nv), r -> setmin(m+1,y,nv);
		}
	}

	void rmq() {
		// cout << s << " "  << e << " " << minv << " " << maxv << "\n";
		if (s == e) ans[s] = minv;
		else {
			push();
			l -> rmq();
			r -> rmq();
		}
	}
}*root;

void buildWall(int n, int Q, int op[], int left[], int right[], int height[], int finalHeight[]){

	root = new node(0,n-1);

	for (int q = 0; q < Q; q++) {
		int t = op[q];
		int l = left[q];
		int r = right[q];
		int h = height[q];
		if (t == 1) { //adding -> set min
			root -> setmin(l,r,h);
		} else {
			root -> setmax(l,r,h);
		}

		// root -> rmq();
		// for (int i = 0; i< n;i++) cout <<ans[i] << " ";
		// cout << "\n";
	}

	root -> rmq();
	for (int i =0;i<n;i++) {
		finalHeight[i] = ans[i];
	}
}

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