Submission #59179

#	Time	Username	Problem	Language	Result	Execution time	Memory
59179		TadijaSebez	Wall (IOI14_wall)	C++11	100 / 100	1512 ms	208664 KiB

wall

#include "wall.h"
#include <stdio.h>
#include <vector>
using namespace std;
#define pb push_back
const int N=2000050;
const int M=2*N;
const int inf=2e9+7;
int ls[M],rs[M],val[M],lzy1[M],lzy2[M],tsz,root;
int min(int a, int b){ return a>b?b:a;}
int max(int a, int b){ return a>b?a:b;}
void Build(int &c, int ss, int se)
{
	c=++tsz;lzy1[c]=0;lzy2[c]=inf;
	if(ss==se) return;
	int mid=ss+se>>1;
	Build(ls[c],ss,mid);
	Build(rs[c],mid+1,se);
}
void Push(int c, int ss, int se)
{
	val[c]=max(val[c],lzy1[c]);
	val[c]=min(val[c],lzy2[c]);
	if(ss!=se)
	{
		lzy1[ls[c]]=max(lzy1[ls[c]],lzy1[c]);
		lzy1[ls[c]]=min(lzy1[ls[c]],lzy2[c]);
		lzy2[ls[c]]=max(lzy2[ls[c]],lzy1[c]);
		lzy2[ls[c]]=min(lzy2[ls[c]],lzy2[c]);
		lzy1[rs[c]]=max(lzy1[rs[c]],lzy1[c]);
		lzy1[rs[c]]=min(lzy1[rs[c]],lzy2[c]);
		lzy2[rs[c]]=max(lzy2[rs[c]],lzy1[c]);
		lzy2[rs[c]]=min(lzy2[rs[c]],lzy2[c]);
	}
	lzy1[c]=0;
	lzy2[c]=inf;
}
void Add(int c, int ss, int se, int qs, int qe, int h)
{
	Push(c,ss,se);
	if(qs>se || ss>qe) return;
	if(qs<=ss && qe>=se){ lzy1[c]=h;return;}
	int mid=ss+se>>1;
	Add(ls[c],ss,mid,qs,qe,h);
	Add(rs[c],mid+1,se,qs,qe,h);
}
void Del(int c, int ss, int se, int qs, int qe, int h)
{
	Push(c,ss,se);
	if(qs>se || ss>qe) return;
	if(qs<=ss && qe>=se){ lzy2[c]=h;return;}
	int mid=ss+se>>1;
	Del(ls[c],ss,mid,qs,qe,h);
	Del(rs[c],mid+1,se,qs,qe,h);
}
int sol[N];
void DFS(int c, int ss, int se)
{
	Push(c,ss,se);
	if(ss==se){ sol[ss]=val[c];return;}
	int mid=ss+se>>1;
	DFS(ls[c],ss,mid);
	DFS(rs[c],mid+1,se);
}
void buildWall(int n, int q, int op[], int l[], int r[], int h[], int ans[])
{
	int i;
	Build(root,1,n);
	for(i=0;i<q;i++)
	{
		l[i]++;r[i]++;
		if(op[i]==1) Add(root,1,n,l[i],r[i],h[i]);
		else Del(root,1,n,l[i],r[i],h[i]);
	}
	DFS(root,1,n);
	for(i=1;i<=n;i++) ans[i-1]=sol[i];
}

Compilation message (stderr)

wall.cpp: In function 'void Build(int&, int, int)':
wall.cpp:16:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
wall.cpp: In function 'void Add(int, int, int, int, int, int)':
wall.cpp:43:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
wall.cpp: In function 'void Del(int, int, int, int, int, int)':
wall.cpp:52:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
wall.cpp: In function 'void DFS(int, int, int)':
wall.cpp:61:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~

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