Submission #420186

#	Time	Username	Problem	Language	Result	Execution time	Memory
420186		Bill_00	Wall (IOI14_wall)	C++14	0 / 100	212 ms	13944 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define N 2000002
#define INF INT_MAX
using namespace std;
int up[N*4],down[N*4],ans[N];
void build(int id,int l,int r){
	if(l==r){
		down[id]=INF;
		return;
	}
	int m=l+r>>1;
	build(id*2,l,m);
	build(id*2+1,m+1,r);
}
void query(int id,int l,int r){
	if(l==r){
		ans[l]=min(up[id],down[id]);
		return;
	}
	int m=l+r>>1;
	query(id*2,l,m);
	query(id*2+1,m+1,r);
}
void update(int id,int l,int r,int L,int R,int op,int H){
	// cout << l << ' ' << r << "\n";
	if(l!=r){
		up[id*2]=max(up[id],up[id*2]);
		up[id*2]=min(up[id*2],down[id]);
		down[id*2]=min(down[id],down[id*2]);
		down[id*2]=max(down[id*2],up[id]);
		up[id*2+1]=max(up[id],up[id*2+1]);
		up[id*2+1]=min(up[id*2+1],down[id]);
		down[id*2+1]=min(down[id],down[id*2+1]);
		down[id*2+1]=max(down[id*2+1],up[id]);
		up[id]=0;
		down[id]=INF;
	}
	if(r<L || R<l){
		return;
	}
	if(L<=l && r<=R){
		if(op==1){
			up[id]=max(up[id],H);
			down[id]=max(down[id],H);
		}
		if(op==2){
			up[id]=min(up[id],H);
			down[id]=min(down[id],H);
		}
		// cout << up[id] << ' ' << down[id] << ' ' << l << ' ' << r << '\n';
		if(l!=r){
			up[id*2]=max(up[id],up[id*2]);
			up[id*2]=min(up[id*2],down[id]);
			down[id*2]=min(down[id],down[id*2]);
			down[id*2]=max(down[id*2],up[id]);
			up[id*2+1]=max(up[id],up[id*2+1]);
			up[id*2+1]=min(up[id*2+1],down[id]);
			down[id*2+1]=min(down[id],down[id*2+1]);
			down[id*2+1]=max(down[id*2+1],up[id]);
			up[id]=0;
			down[id]=INF;
		}
		return;
	}
	int m=l+r>>1;
	update(id*2,l,m,L,R,op,H);
	update(id*2+1,m+1,r,L,R,op,H);
}
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++){
		update(1,0,n-1,left[i],right[i],op[i],height[i]);
	}
	query(1,0,n-1);
	for(int i=0;i<n;i++){
		finalHeight[i]=ans[i];
	}
}

Compilation message (stderr)

wall.cpp: In function 'void build(int, int, int)':
wall.cpp:12:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |  int m=l+r>>1;
      |        ~^~
wall.cpp: In function 'void query(int, int, int)':
wall.cpp:21:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |  int m=l+r>>1;
      |        ~^~
wall.cpp: In function 'void update(int, int, int, int, int, int, int)':
wall.cpp:66:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |  int m=l+r>>1;
      |        ~^~

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