Submission #120766

#	Time	Username	Problem	Language	Result	Execution time	Memory
120766		dorijanlendvaj	Wall (IOI14_wall)	C++14	32 / 100	2541 ms	40968 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define ll long long
using namespace std;
const char en='\n';
const int MOD=1000000007;
#pragma GCC optimize("O2,unroll-loops")

const int N=100010,M=1<<17;

int ee,prop[M*2+10];
pii qu1[M*2+10][5],qu2[M*2+10][5];
int h[N];

inline void maa(int&a,const int&b)
{
	if (b>a) a=b;
}

inline void mii(int&a,const int&b)
{
	if (b<a) a=b;
}

void pus(pii a[],pii x)
{
	int z=4;
	while (z && a[z].x==0) --z;
	if (z==4)
	{
		a[0]={0,0};
		for (int i=0;i<4;++i) a[i]=a[i+1];
		a[4]=x;
	}
	else a[z+1]=x;
}

void pro1(int i)
{
	++ee;
	if (i<M)
	{
		maa(prop[i*2],prop[i]);
		maa(prop[i*2+1],prop[i]);
		prop[i]=0;
		int z=4;
		while (z>=0 && qu1[i][z].x==0) --z;
		while (z>=0)
		{
			pus(qu1[i*2],qu1[i][z]);
			pus(qu1[i*2+1],qu1[i][z]);
			qu1[i][z]={0,0};
			--z;
		}
	}
}

void upd1(int&l,int&r,int&x,int&o,int lo=0,int hi=M,int i=1)
{
	pus(qu1[i],{o,x});
	pro1(i);
	if (lo>=l && hi<=r)
	{
		prop[i]=max(prop[i],x);
		//pro1(i);
		return;
	}
	if (lo>=r || hi<=l) return;
	int mid=(lo+hi)/2;
	upd1(l,r,x,o,lo,mid,i*2);
	upd1(l,r,x,o,mid,hi,i*2+1);
}

void pro2(int i)
{
	++ee;
	if (i<M)
	{
		mii(prop[i*2],prop[i]);
		mii(prop[i*2+1],prop[i]);
		prop[i]=MOD;
		int z=4;
		while (z>=0 && qu2[i][z].x==0) --z;
		while (z>=0)
		{
			pus(qu2[i*2],qu2[i][z]);
			pus(qu2[i*2+1],qu2[i][z]);
			qu2[i][z]={0,0};
			--z;
		}
	}
}

void upd2(int&l,int&r,int&x,int&o,int lo=0,int hi=M,int i=1)
{
	pus(qu2[i],{o,x});
	pro2(i);
	if (lo>=l && hi<=r)
	{
		prop[i]=min(prop[i],x);
		//pro2(i);
		return;
	}
	if (lo>=r || hi<=l) return;
	int mid=(lo+hi)/2;
	upd2(l,r,x,o,lo,mid,i*2);
	upd2(l,r,x,o,mid,hi,i*2+1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	assert(n<=1e5);
	vector<int> res(n);
  if (n*1ll*k<=5e8)
  {
    int z=0;
  	for (int o=0;o<k;++o)
  	{
  		assert(left[o]>=0 && left[o]<n);
  		assert(right[o]>=left[o] && right[o]<n);
  		assert(right[o]-left[o]<n);
  		if (op[o]==1)
  		{
  			for (int i=left[o];i<=right[o];++i) maa(res[i],height[o]);
  		}
  		else
  		{
  			for (int i=left[o];i<=right[o];++i) mii(res[i],height[o]);
  		}
  	}
  	for (int i=0;i<n;++i) finalHeight[i]=res[i];
  	return;
  }
  int o=0;
  for (;o<k && op[o]==1;++o)
  {
  	int x=left[o],y=right[o]+1,z=height[o],w=o+1;
  	upd1(x,y,z,w);
  }
  for (int i=1;i<M;++i) pro1(i);
  for (int i=1;i<M;++i) prop[i]=MOD;
  for (;o<k && op[o]!=1;++o)
  {
  	int x=left[o],y=right[o]+1,z=height[o],w=o+1;
  	upd2(x,y,z,w);
  }
  for (int i=1;i<M;++i) pro2(i);
  for (int i=M;i<M+n;++i) finalHeight[i-M]=prop[i];
}

Compilation message (stderr)

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:119:9: warning: unused variable 'z' [-Wunused-variable]
     int z=0;
         ^

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