Submission #389945

#	Time	Username	Problem	Language	Result	Execution time	Memory
389945		ritul_kr_singh	Wall (IOI14_wall)	C++17	100 / 100	970 ms	67240 KiB

wall

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define sp << ' ' <<
#define nl << '\n'
#include "wall.h"

const int INF = 1e18;

struct SegmentTree{
	using T = array<int, 2>;
	vector<T> a;
	int sz = 1;
	T ID = {0, INF};
	SegmentTree(int n){
		while(sz < n) sz += sz;
		a.assign(2*sz, ID);
	}
	void apply(T &x, T &y){
		y[0] = max(y[0], x[0]);
		y[1] = max(y[1], x[0]);
		y[0] = min(y[0], x[1]);
		y[1] = min(y[1], x[1]);
	}
	void push(int x){
		if(a[x] == ID) return;
		if(x+1<sz){
			apply(a[x], a[2*x+1]);
			apply(a[x], a[2*x+2]);
			a[x] = ID;
		}
	}
	void update(int l, int r, T v, int x, int lx, int rx){
		push(x);
		if(r<=lx or rx<=l) return;
		if(l<=lx and rx<=r) return apply(v, a[x]);
		int mx = (lx+rx)/2;
		update(l, r, v, 2*x+1, lx, mx);
		update(l, r, v, 2*x+2, mx, rx);
	}
	void update(int l, int r, int low, int high){
		T v = {low, high};
		update(l, r+1, v, 0, 0, sz);
	}
	void build(vector<int> &ans, int n, int x, int lx, int rx){
		push(x);
		if(rx-lx==1){
			// cout << a[x][0] nl;
			if(lx<n) ans[lx] = a[x][0];
			return;
		}
		int mx = (lx+rx)/2;
		build(ans, n, 2*x+1, lx, mx);
		build(ans, n, 2*x+2, mx, rx);
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	SegmentTree st(n);
	for(int i=0; i<k; ++i){
		// cout << op[i] sp left[i] sp right[i] sp height[i] nl;
		if(op[i]==1) st.update(left[i], right[i], height[i], INF);
		else st.update(left[i], right[i], 0, height[i]);
	}
	vector<int> ans(n);

	st.build(ans, n, 0, 0, st.sz);
	for(int i=0; i<n; ++i) finalHeight[i] = ans[i];
}

Compilation message (stderr)

wall.cpp:8:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    8 | const int INF = 1e18;
      |                 ^~~~

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