oj.uz

Submission #120766

# Submission time Handle Problem Language Result Execution time Memory
120766 2019-06-25T12:18:38 Z dorijanlendvaj Wall (IOI14_wall) C++14
32 / 100
 2541 ms 40968 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);
  for (int i=M;i<M+n;++i) finalHeight[i-M]=prop[i];
}

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 256 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 3 ms 356 KB Output is correct
4 Correct 12 ms 640 KB Output is correct
5 Correct 13 ms 640 KB Output is correct
6 Correct 13 ms 668 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 145 ms 14100 KB Output is correct
3 Correct 833 ms 28840 KB Output is correct
4 Correct 2461 ms 39996 KB Output is correct
5 Correct 1075 ms 40912 KB Output is correct
6 Correct 1060 ms 39396 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 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 560 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 256 KB Output is correct
8 Correct 141 ms 13944 KB Output is correct
9 Correct 805 ms 28836 KB Output is correct
10 Correct 2464 ms 39976 KB Output is correct
11 Correct 1065 ms 40920 KB Output is correct
12 Correct 1057 ms 39272 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 145 ms 14076 KB Output is correct
15 Incorrect 30 ms 12280 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 256 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 612 KB Output is correct
6 Correct 12 ms 640 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 142 ms 13988 KB Output is correct
9 Correct 809 ms 28804 KB Output is correct
10 Correct 2541 ms 39960 KB Output is correct
11 Correct 1080 ms 40968 KB Output is correct
12 Correct 1081 ms 39360 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 149 ms 14044 KB Output is correct
15 Incorrect 39 ms 12408 KB Output isn't correct
16 Halted 0 ms 0 KB -