Submission #438419

#	Time	Username	Problem	Language	Result	Execution time	Memory
438419		adamjinwei	Wall (IOI14_wall)	C++14	100 / 100	978 ms	86088 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define inf 1000000007
#define mod 1000000007
#define lson (p<<1)
#define rson (p<<1|1)
#define rnd() rand_num()
#define bigrnd() dis(rand_num)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
//#define int long long
using namespace std;
unsigned sed=std::chrono::system_clock::now().time_since_epoch().count();
mt19937 rand_num(sed);
uniform_int_distribution<long long> dis(0,inf);
template <typename T> void read(T &x){
	x=0;char ch=getchar();int fh=1;
	while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
	while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=fh;
}
template <typename T> void write(T x) {
	if (x<0) x=-x,putchar('-');
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int mx[8000005],mn[8000005],tag[8000005];
void pushup(int p)
{
	mx[p]=max(mx[lson],mx[rson]);
	mn[p]=min(mn[lson],mn[rson]);
}
void build(int p,int l,int r)
{
	if(l==r)
	{
		mx[p]=mn[p]=0;
		tag[p]=-1;
		return;
	}
	int mid=l+r>>1;
	build(lson,l,mid);
	build(rson,mid+1,r);
	pushup(p);
}
void pushdown(int p)
{
	if(tag[p]!=-1)
	{
		mx[lson]=mn[lson]=tag[lson]=mx[rson]=mn[rson]=tag[rson]=tag[p];
		tag[p]=-1;
	}
}
void add(int p,int l,int r,int x,int y,int k)
{
	if(mn[p]>=k) return;
	if(x<=l&&r<=y)
	{
		if(mx[p]<=k)
		{
			mx[p]=mn[p]=tag[p]=k;
			return;
		}
	}
	pushdown(p);
	int mid=l+r>>1;
	if(x<=mid) add(lson,l,mid,x,y,k);
	if(mid+1<=y) add(rson,mid+1,r,x,y,k);
	pushup(p);
}
void remove(int p,int l,int r,int x,int y,int k)
{
	if(mx[p]<=k) return;
	if(x<=l&&r<=y)
	{
		if(mn[p]>=k)
		{
			mx[p]=mn[p]=tag[p]=k;
			return;
		}
	}
	pushdown(p);
	int mid=l+r>>1;
	if(x<=mid) remove(lson,l,mid,x,y,k);
	if(mid+1<=y) remove(rson,mid+1,r,x,y,k);
	pushup(p);
}
int query(int p,int l,int r,int x)
{
	if(l==r)
		return mx[p];
	pushdown(p);
	int mid=l+r>>1;
	if(x<=mid) return query(lson,l,mid,x);
	else return query(rson,mid+1,r,x);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
	build(1,1,n);
	for(int i=0;i<k;++i)
	{
		if(op[i]==1)
			add(1,1,n,left[i]+1,right[i]+1,height[i]);
		else
			remove(1,1,n,left[i]+1,right[i]+1,height[i]);
	}
	for(int i=0;i<n;++i)
		finalHeight[i]=query(1,1,n,i+1);
}

Compilation message (stderr)

wall.cpp: In function 'void build(int, int, int)':
wall.cpp:45:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |  int mid=l+r>>1;
      |          ~^~
wall.cpp: In function 'void add(int, int, int, int, int, int)':
wall.cpp:70:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |  int mid=l+r>>1;
      |          ~^~
wall.cpp: In function 'void remove(int, int, int, int, int, int)':
wall.cpp:87:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |  int mid=l+r>>1;
      |          ~^~
wall.cpp: In function 'int query(int, int, int, int)':
wall.cpp:97:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |  int mid=l+r>>1;
      |          ~^~

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