Submission #870846

#	Time	Username	Problem	Language	Result	Execution time	Memory
870846		Hyojin	Wall (IOI14_wall)	C++17	100 / 100	1213 ms	104604 KiB

wall

#include <bits/stdc++.h>
using namespace std;
#define bit(n,i) ((n>>i)&1) 
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define ep emplace_back
#define pii pair<int,int>
#define piii pair<int,pii> 
#define fi first
#define se second
#define ll long long
#define debug(x) cerr << #x << ' ' << x << '\n'
#define dbg(x) cerr<<#x<<' '<<x<<' '
const int base=31;								
const int MOD=1e9+7;	
const int N=1e6+5;
const int INF=1e9;
const int mx=2e6;
struct segtree{
	int max1,max2,min1,min2;
} st[mx*4+5];
int n,m,k;
array<int,4>queries[N];
void pushMin(int id,int val)
{
	if (st[id].min1>=val)
	{
		st[id]={val,-INF,val,INF};
	}
	else if (val<st[id].max1)
	{
		if (st[id].min2==st[id].max1) st[id].min2=val;
		st[id].max1=val;
	}
}
void pushMax(int id,int val)
{
	if (st[id].max1<=val)
	{
		st[id]={val,-INF,val,INF};
	}
	else if (st[id].min1<val)
	{
		if (st[id].max2==st[id].min1) st[id].max2=val;
		st[id].min1=val;
	}
}
void up(int id)
{
	st[id].max1=max(st[id<<1].max1,st[id<<1|1].max1);
	st[id].max2=max(st[id<<1].max2,st[id<<1|1].max2);
	st[id].min1=min(st[id<<1].min1,st[id<<1|1].min1);
	st[id].min2=min(st[id<<1].min2,st[id<<1|1].min2);
	if (st[id<<1].max1!=st[id].max1) st[id].max2=max(st[id].max2,st[id<<1].max1);
	if (st[id<<1|1].max1!=st[id].max1) st[id].max2=max(st[id].max2,st[id<<1|1].max1);
	if (st[id<<1].min1!=st[id].min1) st[id].min2=min(st[id].min2,st[id<<1].min1);
	if (st[id<<1|1].min1!=st[id].min1) st[id].min2=min(st[id].min2,st[id<<1|1].min1);
}
void down(int id)
{
	pushMin(id<<1,st[id].max1);
	pushMin(id<<1|1,st[id].max1);
	pushMax(id<<1,st[id].min1);
	pushMax(id<<1|1,st[id].min1);
}
void updateMax(int id,int l,int r,int u,int v,int x)
{
	if (v<l||r<u||x<=st[id].min1) return;
	if (u<=l&&r<=v&&x<st[id].min2)
	{
		pushMax(id,x);
		return;
	}
	int mid=l+r>>1;
	down(id);
	updateMax(id<<1,l,mid,u,v,x);
	updateMax(id<<1|1,mid+1,r,u,v,x);
	up(id);
}
void updateMin(int id,int l,int r,int u,int v,int x)
{
	if (v<l||r<u||x>=st[id].max1) return;
	if (u<=l&&r<=v&&st[id].max2<x)
	{
		pushMin(id,x);
		return;
	}
	int mid=l+r>>1;
	down(id);
	updateMin(id<<1,l,mid,u,v,x);
	updateMin(id<<1|1,mid+1,r,u,v,x);
	up(id);
}
int get(int id,int l,int r,int x)
{
	if (l==r) return st[id].max1;
	int mid=l+r>>1;
	down(id);
	if (x<=mid) return get(id<<1,l,mid,x);
	return get(id<<1|1,mid+1,r,x);
}
void build(int id,int l,int r)
{
	if (l==r)
	{
		st[id]={0,-INF,0,INF};
		return;
	}
	int mid=l+r>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	up(id);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
	build(1,0,n-1);
	for (int i=0;i<k;i++)
	{
		if (op[i]==1)
		{
			updateMax(1,0,n-1,left[i],right[i],height[i]);
		} else updateMin(1,0,n-1,left[i],right[i],height[i]);
	}
	for (int i=0;i<n;i++)
	{
		finalHeight[i]=get(1,0,n-1,i);
	}
}
/* stuff you should look for						
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message (stderr)

wall.cpp: In function 'void updateMax(int, int, int, int, int, int)':
wall.cpp:74:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |  int mid=l+r>>1;
      |          ~^~
wall.cpp: In function 'void updateMin(int, int, int, int, int, int)':
wall.cpp:88:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |  int mid=l+r>>1;
      |          ~^~
wall.cpp: In function 'int get(int, int, int, int)':
wall.cpp:97:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |  int mid=l+r>>1;
      |          ~^~
wall.cpp: In function 'void build(int, int, int)':
wall.cpp:109:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |  int mid=l+r>>1;
      |          ~^~

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