Submission #541325

#	Time	Username	Problem	Language	Result	Execution time	Memory
541325		starchan	Wall (IOI14_wall)	C++17	0 / 100	410 ms	262144 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF 1e9+1e8
#define zero (int)0
#define MX (int)3e5+5
#define LMX (int)1e7
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL);
const int mod = 1e9+7; //may change to that 99.. number.
struct mx_mn_iser_segment_tree
{
	vector<int> smx;
	vector<int> mx;
	vector<int> smn;
	vector<int> mn;
	vector<int> mxlazy;
	vector<int> mnlazy;
	void init()
	{
		smx.assign(LMX, -INF);
		mx.assign(LMX, 0);
		smn.assign(LMX, INF);
		mn.assign(LMX, 0);
		mxlazy.assign(LMX, -INF);
		mnlazy.assign(LMX, INF);
	}
	void mx_push(int id)
	{
		if(mn[2*id] == mn[id])
			mnlazy[2*id] = max(mnlazy[2*id], mnlazy[id]);
		if(mn[2*id+1] == mn[id])
			mnlazy[2*id+1] = max(mnlazy[2*id+1], mnlazy[id]);
		mnlazy[id] = -INF;
		return;
	}
	void mn_push(int id)
	{
		if(mx[2*id] == mx[id])
			mxlazy[2*id] = min(mxlazy[2*id], mxlazy[id]);
		if(mx[2*id+1] == mx[id])
			mxlazy[2*id+1] = min(mxlazy[2*id+1], mxlazy[id]);
		mxlazy[id] = INF;
		return;
	}
	int fix(int id)
	{
		mn[id] = min(mn[2*id], mn[2*id+1]);
		int turbo1 = min(smn[2*id], smn[2*id+1]);
		if(mn[2*id]==mn[2*id+1])
			smn[id] = turbo1;
		else
			smn[id] = min(mn[2*id]+mn[2*id+1]-mn[id], turbo1);
		mx[id] = max(mx[2*id], mx[2*id+1]);
		int turbo2 = max(smx[2*id], smx[2*id+1]);
		if(mx[2*id]==mx[2*id+1])
			smx[id] = turbo2;
		else
			smx[id] = max(mx[2*id]+mx[2*id+1]-mx[id], turbo2);
	}
	void mx_update(int x, int ql, int qr, int id, int l, int r)
	{
		if(r < ql || qr < l)
			return;
		if((l <= ql) && (r <= qr) && (x < smn[id]))
		{
			if(x <= mn[id])
				return;
			mn[id] = max(mn[id], x);
			mnlazy[id] = max(mnlazy[id], x);
			return;
		}
		mx_push(id);
		int m = (l+r)/2;
		mx_update(x, ql, qr, 2*id, l, m);
		mx_update(x, ql, qr, 2*id+1, m+1, r);
		fix(id);	
		return;
	}
	void mn_update(int x, int ql, int qr, int id, int l, int r)
	{
		if(r < ql || qr < l)
			return;
		if((l <= ql) && (r <= qr) && (x < smx[id]))
		{
			if(x <= mx[id])
				return;
			mx[id] = max(mx[id], x);
			mxlazy[id] = max(mxlazy[id], x);
			return;
		}
		mn_push(id);
		int m = (l+r)/2;
		mn_update(x, ql, qr, 2*id, l, m);
		mn_update(x, ql, qr, 2*id+1, m+1, r);
		fix(id);	
		return;
	}
	int val(int pos, int id, int l, int r)
	{
		if(l==r)
			return mx[id];
		mn_push(id);
		mx_push(id);
		int m = (l+r)/2;
		if(pos <= m)
			return val(pos, 2*id, l, m);
		else
			return val(pos, 2*id+1, m+1, r);
	}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	mx_mn_iser_segment_tree work;
	work.init();
	for(int i = 0; i < k; i++)
	{
		if(op[i] == 1)
			work.mx_update(height[i], left[i], right[i], 1, 0, n);
		else
			work.mn_update(height[i], left[i], right[i], 1, 0, n);
	}
	for(int i = 0; i < n; i++)
		finalHeight[i] = work.val(i, 1, 0, n);
	return;
}

Compilation message (stderr)

wall.cpp: In member function 'int mx_mn_iser_segment_tree::fix(int)':
wall.cpp:64:2: warning: no return statement in function returning non-void [-Wreturn-type]
   64 |  }
      |  ^

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