Submission #854549

#	Time	Username	Problem	Language	Result	Execution time	Memory
854549		KN200711	Wall (IOI14_wall)	C++14	100 / 100	649 ms	79984 KiB

wall

#include "wall.h"
# include <bits/stdc++.h>
using namespace std;

const int MXN = 2e6;
int bl[4 * MXN + 1], br[4 * MXN + 1];

void build(int lf, int rg, int nd) {
	bl[nd] = br[nd] = 0;
	if(lf != rg) {
		int mid = (lf + rg) / 2;
		build(lf, mid, 2*nd+1);
		build(mid+1, rg, 2*nd+2);
	}
}

void upd_lazy(int lf, int rg, int nd) {
	if(lf != rg) {
		int mid = (lf + rg) / 2;
		if(bl[2*nd+1] > bl[nd]) bl[2*nd+1] = bl[nd];
		else if(bl[2*nd+1] < br[nd]) bl[2*nd+1] = br[nd];
		
		if(bl[2*nd+2] > bl[nd]) bl[2*nd+2] = bl[nd];
		else if(bl[2*nd+2] < br[nd]) bl[2*nd+2] = br[nd];
		
		if(br[2*nd+1] > bl[nd]) br[2*nd+1] = bl[nd];
		else if(br[2*nd+1] < br[nd]) br[2*nd+1] = br[nd];
		
		if(br[2*nd+2] > bl[nd]) br[2*nd+2] = bl[nd];
		else if(br[2*nd+2] < br[nd]) br[2*nd+2] = br[nd];
	}
}

void upd(int lf, int rg, int nd, int clf, int crg, int op, int pos) {
	upd_lazy(lf, rg, nd);
	if(clf > rg || lf > crg) return;
	else if(clf <= lf && rg <= crg) {
		if(op == 1) {
		//	cout<<"upd : "<<lf<<" "<<rg<<" "<<nd<<" "<<bl[nd]<<" "<<pos<<endl;
			if(bl[nd] <= pos) bl[nd] = br[nd] = pos;
			else if(br[nd] <= pos) br[nd] = pos;
		} else {
			if(br[nd] >= pos) bl[nd] = br[nd] = pos;
			else if(bl[nd] >= pos) bl[nd] = pos;
		}
		upd_lazy(lf, rg, nd);
	} else {
		int mid = (lf + rg) / 2;
		upd(lf, mid, 2*nd+1, clf, crg, op, pos);
		upd(mid+1, rg, 2*nd+2, clf, crg, op, pos);
		bl[nd] = max(bl[2*nd+1], bl[2*nd+2]);
		br[nd] = min(br[2*nd+1], br[2*nd+2]);
	}
}

int val[MXN + 1];

void fn(int lf, int rg, int nd) {
	upd_lazy(lf, rg, nd);
	if(lf == rg) {
		val[lf] = bl[nd];
	} else {
		int mid = (lf + rg) / 2;
		fn(lf, mid, 2*nd+1);
		fn(mid+1, rg, 2*nd+2);
	}
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	build(0, n-1, 0);
	for(int i=0;i<k;i++) {
		upd(0, n-1, 0, left[i], right[i], op[i], height[i]);
	}
	fn(0, n-1, 0);
	for(int i=0;i<n;i++) finalHeight[i] = val[i];
}

Compilation message (stderr)

wall.cpp: In function 'void upd_lazy(int, int, int)':
wall.cpp:19:7: warning: unused variable 'mid' [-Wunused-variable]
   19 |   int mid = (lf + rg) / 2;
      |       ^~~

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