Submission #52103

#	Time	Username	Problem	Language	Result	Execution time	Memory
52103		shoemakerjo	Wall (IOI14_wall)	C++14	0 / 100	372 ms	216004 KiB

wall

#include "wall.h"
#include <cmath>
#include <vector>

using namespace std;
#define maxn 2000010
#define maxk 500010

int seg[maxk][3]; //store over the three

//seg[i][0] is for range ops
//seg[i][1] is for number of maxes
//seg[i][2] is for number of mins
//result is always stored in seg[0][0]
//-1 will be used to signify that nothing happens

int N, K;
int type[maxk];
int val[maxk];
vector< vector<int> > activate(maxn);
vector< vector<int> > deactivate(maxn);

void upm(int spot, int diff, int ind, int ss, int se, int si) {
	if (spot > se || spot < ss) return;
	if (ss == se) {
		seg[si][ind] += diff;
		return;
	}
	int mid = (ss+se)/2;
	seg[si][ind] += diff; //you know it is in this range
	if (spot <= mid) {
		upm(spot, diff, ind, ss, mid, si*2+1);
	}
	else {
		upm(spot, diff, ind, mid+1, se, si*2+2);
	}
}

void updatem(int spot, int diff, int ind) {
	upm(spot, diff, ind, 0, K, 0);
}

void up(int spot, bool flip, int ss, int se, int si) {
	if (spot < ss || spot > se) return;
	if (ss == se) {
		if (flip) {
			seg[si][0] = ss;
		}
		else seg[si][0] = -1;
		return;
	}
	int mid = (ss+se)/2;
	if (spot <= mid) up(spot, flip, ss, mid, si*2+1);
	else up(spot, flip, mid+1, se, si*2+2);
	//now we must merge range
	int ole = seg[si*2+1][0];
	int ori = seg[si*2+2][0];
	if (ole == -1) {
		seg[si][0] = ori;
		return;
	}
	if (ori == -1) {
		seg[si][0] = ole;
		return;
	}
	int lval = val[ole];
	int rval = val[ori];
	int lt = type[ole];
	int rt = type[ori];
	if (rt == 1) {
		if (lval <= rval) {
			seg[si][0] = ori;
			return;
		}
		if (seg[si*2+2][2] > 0) {
			//there is a min in the right chunk
			seg[si][0] = ori;
			return;
		}
		seg[si][0] = ole;
		return;
	}
	else { //rt is 2 (a min)
		if (lval >= rval) {
			seg[si][0] = ori;
			return;
		}
		if (seg[si*2+2][1] > 0) {
			//there is a max in the right
			seg[si][0] = ori;
			return;
		}
		seg[si][0] = ole;
		return;
	}
}

void update(int spot, bool flip) { 
	//flip is true if you turn it on, false if not

	//have to reprocess all ranges with this thing in it
	up(spot, flip, 0, K, 0);
}

void buildWall(int n, int k, int op[], int left[], 
	int right[], int height[], int finalHeight[]){

	N = n;
	K = k;

	for (int i = 0; i < maxk; i++) {
		seg[i][0] = -1;
		seg[i][1] = seg[i][2] = 0;
	}

	update(0, true); // i think this is good

	type[0] = 1;
	val[0] = 0;

	for (int i = 0; i < k; i++) {
		type[i+1] = op[i];
		val[i+1] = height[i];
		activate[left[i]].push_back(i+1);
		deactivate[right[i]+1].push_back(i+1);
	}

	for (int i = 0; i < n; i++) {
		//process things and then fill my finalheight
		for (int j = 0; j < activate[i].size(); j++) {
			int v = activate[i][j];
			updatem(v, 1, type[v]);
			update(v, true);
		}
		for (int j = 0; j < deactivate[i].size(); j++) {
			int v = deactivate[i][j];
			updatem(v, -1, type[v]);
			update(v, false);
		}

		//do some stuff above this
		finalHeight[i] = val[seg[0][0]];

	}

  	return;
}

Compilation message (stderr)

wall.cpp: In function 'void up(int, bool, int, int, int)':
wall.cpp:68:6: warning: unused variable 'lt' [-Wunused-variable]
  int lt = type[ole];
      ^~
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:130:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < activate[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~~~~~~~
wall.cpp:135:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < deactivate[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~~~~~~~~~

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