Submission #373759

#	Time	Username	Problem	Language	Result	Execution time	Memory
373759		sofapuden	Wall (IOI14_wall)	C++14	100 / 100	1006 ms	216972 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e6+5;
const int maxv = 1<<30;

struct seg{
	
	seg *r, *l;
	int lb, rb;
	bool ch;
	int mxval, mnval;
	int mid;

	seg () : l(NULL), r(NULL), ch(false), mnval(0), mxval(maxv) {}
	

	void init(int lx, int rx){
		lb = lx, rb = rx;
		mid = (lx+rx)>>1;
	}

	void ex(){
		if(r == NULL){
			r = new seg;
			r->init(mid+1,rb);
		}
		if(l == NULL){
			l = new seg;
			l->init(lb,mid);
		}
	}
	void push(){
		r->mxval = min(r->mxval,mxval);
		r->mnval = min(r->mnval,r->mxval);
		r->mnval = max(r->mnval,mnval);
		r->mxval = max(r->mxval,r->mnval);
		r->ch = true;
		l->mxval = min(l->mxval,mxval);
		l->mnval = min(l->mnval,l->mxval);
		l->mnval = max(l->mnval,mnval);
		l->mxval = max(l->mxval,l->mnval);
		l->ch = true;
		mnval = 0;
		mxval = maxv;
		ch = false;
	}

	void add(int cl, int cr, int am){
		if(lb > cr || rb < cl)return;
		if(lb >= cl && rb <= cr){
			mnval = max(mnval,am);
			mxval = max(mxval,mnval);
			ch = true;
			return;
		}
		ex();
		if(ch)push();
		l->add(cl,cr,am);
		r->add(cl,cr,am);
	}
	void rem(int cl, int cr, int am){
		if(lb > cr || rb < cl)return;
		if(lb >= cl && rb <= cr){
			mxval = min(mxval,am);
			mnval = min(mnval,mxval);
			ch = true;
			return;
		}
		ex();
		if(ch)push();
		l->rem(cl,cr,am);
		r->rem(cl,cr,am);
	}
	int fin(int x){
		if(lb == rb){
			return mnval;
		}
		ex();
		if(ch)push();
		if(x > mid)return r->fin(x);
		return l->fin(x);
	}	
};

seg *root = new seg;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	root->init(0,n-1);
	for(int i = 0; i < k; ++i){
		if(op[i] == 1){
			root->add(left[i],right[i],height[i]);
		}
		else{
			root->rem(left[i],right[i],height[i]);
		}
	}
	for(int i = 0; i < n; ++i){
		finalHeight[i] = root->fin(i);
	}
	return;
	
}

Compilation message (stderr)

wall.cpp: In constructor 'seg::seg()':
wall.cpp:11:11: warning: 'seg::l' will be initialized after [-Wreorder]
   11 |  seg *r, *l;
      |           ^
wall.cpp:11:7: warning:   'seg* seg::r' [-Wreorder]
   11 |  seg *r, *l;
      |       ^
wall.cpp:17:2: warning:   when initialized here [-Wreorder]
   17 |  seg () : l(NULL), r(NULL), ch(false), mnval(0), mxval(maxv) {}
      |  ^~~
wall.cpp:14:13: warning: 'seg::mnval' will be initialized after [-Wreorder]
   14 |  int mxval, mnval;
      |             ^~~~~
wall.cpp:14:6: warning:   'int seg::mxval' [-Wreorder]
   14 |  int mxval, mnval;
      |      ^~~~~
wall.cpp:17:2: warning:   when initialized here [-Wreorder]
   17 |  seg () : l(NULL), r(NULL), ch(false), mnval(0), mxval(maxv) {}
      |  ^~~

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