oj.uz

Submission #120767

# Submission time Handle Problem Language Result Execution time Memory
120767 2019-06-25T12:22:40 Z dorijanlendvaj Wall (IOI14_wall) C++14
32 / 100
 2563 ms 31288 KB 
#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);
  if (o==k) for (int i=M;i<M+n;++i) finalHeight[i-M]=prop[i];
  else
  {
  	for (int i=1;i<M;++i) pro1(i);
  	for (int i=0;i<n;++i)
  	{
  		vector<pair<pii,bool>> z;
  		for (int j=0;j<5;++j) z.pb({qu1[i+M][j],0});
  		for (int j=0;j<5;++j) z.pb({qu2[i+M][j],1});
  		sort(z.begin(),z.end());
  		int u=0;
  		for (auto a: z)
  		{
  			if (a.y==0) u=max(u,a.x.y);
  			else u=min(u,a.x.y);
  		}
  		finalHeight[i]=u;
  	}
  }
}

Compilation message

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 12 ms 640 KB Output is correct
5 Correct 12 ms 640 KB Output is correct
6 Correct 12 ms 640 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 139 ms 8464 KB Output is correct
3 Correct 816 ms 25180 KB Output is correct
4 Correct 2563 ms 30632 KB Output is correct
5 Correct 1132 ms 30944 KB Output is correct
6 Correct 1075 ms 31024 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 14 ms 640 KB Output is correct
5 Correct 12 ms 640 KB Output is correct
6 Correct 12 ms 640 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 140 ms 8452 KB Output is correct
9 Correct 842 ms 25208 KB Output is correct
10 Correct 2542 ms 30724 KB Output is correct
11 Correct 1101 ms 30932 KB Output is correct
12 Correct 1084 ms 31288 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 143 ms 8440 KB Output is correct
15 Incorrect 37 ms 12536 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 424 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 12 ms 640 KB Output is correct
5 Correct 12 ms 640 KB Output is correct
6 Correct 13 ms 640 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 139 ms 8440 KB Output is correct
9 Correct 835 ms 25188 KB Output is correct
10 Correct 2521 ms 30376 KB Output is correct
11 Correct 1119 ms 30672 KB Output is correct
12 Correct 1091 ms 30708 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 145 ms 8156 KB Output is correct
15 Incorrect 36 ms 12280 KB Output isn't correct
16 Halted 0 ms 0 KB -