Submission #489625

#	Time	Username	Problem	Language	Result	Execution time	Memory
489625		ssense	Wall (IOI14_wall)	C++14	100 / 100	701 ms	229964 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<ll>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define nax 200005
#define pb push_back
#define sc second
#define fr first
//#define int long long
//#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
class SegmentTree{
public:
	//DEFINITIONS
	int N, sz, lim;
	vector<pair<ll, ll>> lazy;
	//BUILDING
	SegmentTree(int n)
	{
		N = n;
		sz = 6*N;
		lazy.assign(6*N+1, {MXL, 0});
	}
	vint get(int k)
	{
		for(int i = 1; i <= N+k; i++)
		{
			push(i);
		}
		vint ans;
		for(int i = k+1; i < N+k+1; i++)
		{
			ans.pb(min(lazy[i].fr, lazy[i].sc));
		}
		return ans;
	}
	void push(int v)
	{
		lazy[2*v].fr = min(lazy[2*v].fr, lazy[v].fr);
		lazy[2*v].fr = max(lazy[2*v].fr, lazy[v].sc);
		lazy[2*v].sc = max(lazy[2*v].sc, lazy[v].sc);
		lazy[2*v].sc = min(lazy[2*v].sc, lazy[v].fr);
		lazy[2*v+1].fr = min(lazy[2*v+1].fr, lazy[v].fr);
		lazy[2*v+1].fr = max(lazy[2*v+1].fr, lazy[v].sc);
		lazy[2*v+1].sc = max(lazy[2*v+1].sc, lazy[v].sc);
		lazy[2*v+1].sc = min(lazy[2*v+1].sc, lazy[v].fr);
	}
	void update1(int v, int tl, int tr, int l, int r, ll addend)
	{
		if (l > r){return;}
		if (l == tl && tr == r)
		{
			lazy[v].fr = max(lazy[v].fr, addend);
			lazy[v].sc = max(lazy[v].sc, addend);
			return;
		}
		else
		{
			push(v);
			lazy[v].fr = MXL;
			lazy[v].sc = 0;
			int tm = (tl + tr) / 2;
			update1(v*2, tl, tm, l, min(r, tm), addend);
			update1(v*2+1, tm+1, tr, max(l, tm+1), r, addend);
		}
	}
	void update2(int v, int tl, int tr, int l, int r, ll addend)
	{
		if (l > r){return;}
		if (l == tl && tr == r)
		{
			lazy[v].fr = min(lazy[v].fr, addend);
			lazy[v].sc = min(lazy[v].sc, addend);
			return;
		}
		else
		{
			push(v);
			lazy[v].fr = MXL;
			lazy[v].sc = 0;
			int tm = (tl + tr) / 2;
			update2(v*2, tl, tm, l, min(r, tm), addend);
			update2(v*2+1, tm+1, tr, max(l, tm+1), r, addend);
		}
	}
};


void buildWall(int n, int k, int type[], int l[], int r[], int h[], int finalHeight[])
{
	SegmentTree st(n);
	int kk = 1;
	while(kk < n)
	{
		kk*=2;
	}
	for(int i = 0; i < k; i++)
	{
		if(type[i] == 1)
		{
			st.update1(1, 1, kk, l[i]+1, r[i]+1, h[i]);
		}
		else
		{
			st.update2(1, 1, kk, l[i]+1, r[i]+1, h[i]);
		}
	}
	kk--;
	vint ans = st.get(kk);
	for(int i = 0; i < n; i++)
	{
		finalHeight[i] = ans[i];
	}
}
/*
int32_t main(){
	startt
	int t = 1;
	//cin >> t;
	while (t--) {
		solve();
	}
}
*/
/*
 7 3
 4 1 3 4 0 2 3
 
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
 
10 1
1 1 8 4
 */

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