Submission #1013842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013842		parsadox2	Wall (IOI14_wall)	C++17	24 / 100	264 ms	21376 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

const int N = 2e6 + 10;

int n;

struct SEG{
	int L[N << 2] , R[N << 2];
	void Build(int node = 1 , int nl = 0 , int nr = n)
	{
		L[node] = 0;
		R[node] = N;
		if(nr - nl == 1)
			return;
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Build(lc , nl , mid);  Build(rc , mid , nr);
	}
	void Shift(int node , int lc , int rc)
	{
		L[lc] = max(L[lc] , L[node]);
		R[lc] = min(R[lc] , R[node]);
		L[rc] = max(L[rc] , L[node]);
		R[rc] = min(R[rc] , R[node]);
		if(R[lc] < L[lc])
		{
			if(R[lc] == R[node])
				L[lc] = R[node];
			else
				R[lc] = L[node];
		}
		if(R[rc] < L[rc])
		{
			if(R[rc] == R[node])
				L[rc] = R[node];
			else
				R[lc] = L[node];
		}
		L[node] = 0;
		R[node] = N;
	}
	void Min(int l , int r , int val , int node = 1 , int nl = 0 , int nr = n)
	{
		if(r <= nl || nr <= l)
			return;
		if(l <= nl && nr <= r)
		{
			R[node] = min(R[node] , val);
			if(R[node] < L[node])
				L[node] = R[node];
			return;
		}
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Shift(node , lc , rc);
		Min(l , r , val , lc , nl , mid);
		Min(l , r , val , rc , mid , nr);
	}
	void Max(int l , int r , int val , int node = 1 , int nl = 0 , int nr = n)
	{
		if(r <= nl || nr <= l)
			return;
		if(l <= nl && nr <= r)
		{
			L[node] = max(L[node] , val);
			if(R[node] < L[node])
				R[node] = L[node];
			return;
		}
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Shift(node , lc , rc);
		Max(l , r , val , lc , nl , mid);
		Max(l , r , val , rc , mid , nr);
	}
	int Get(int id , int node = 1 , int nl = 0 , int nr = n)
	{
		if(nr - nl == 1)
			return L[node];
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Shift(node , lc , rc);
		if(id < mid)
			return Get(id , lc , nl , mid);
		else
			return Get(id , rc , mid , nr);
	}
	void Debug(int node = 1 , int nl = 0 , int nr = n)
	{
		cout << node << " " << nl << " " << nr << " : " << L[node] << " " << R[node] << endl;
		if(nr - nl == 1)
			return;
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Debug(lc , nl , mid);
		Debug(rc , mid , nr);
	}
} seg;

void buildWall(int nn, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	n = nn;
	seg.Build();
	for(int i = 0 ; i < k ; i++)
	{
		if(op[i] == 1)
			seg.Max(left[i] , right[i] + 1 , height[i]);
		else
			seg.Min(left[i] , right[i] + 1 , height[i]);
		//seg.Debug();
		//cout << endl;
	}
	for(int i = 0 ; i < n ; i++)
		finalHeight[i] = seg.Get(i);
}

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