oj.uz

Submission #52107

# Submission time Handle Problem Language Result Execution time Memory
52107 2018-06-23T23:45:00 Z shoemakerjo Wall (IOI14_wall) C++14
0 / 100
 572 ms 133716 KB 
#include "wall.h"
#include <cmath>
#include <vector>

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

int seg[maxk*4][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, bool flip, int ind, int ss, int se, int si) {
	if (spot > se || spot < ss) return;
	if (ss == se) {
		if (flip) {
			seg[si][ind] = val[ss];
		}
		else {
			seg[si][ind] = -1;
		}
		return;
	}
	int mid = (ss+se)/2;
	// seg[si][ind] += diff; //you know it is in this range
	if (spot <= mid) {
		upm(spot, flip, ind, ss, mid, si*2+1);
	}
	else {
		upm(spot, flip, ind, mid+1, se, si*2+2);
	}
	if (ind == 1) {
		seg[si][ind]  = max(seg[si*2+1][ind], seg[si*2+2][ind]);
	}
	else {
		seg[si][ind] = seg[si*2+1][ind];
		if (seg[si][ind] == -1 || seg[si*2+2][ind] != -1 && seg[si*2+2][ind] < seg[si][ind]) {
			seg[si][ind] = seg[si*2+2][ind];
		}

	}
}

void updatem(int spot, bool flip, int ind) {
	upm(spot, flip, 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] = spot;
		}
		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) { //set to non nothing happens thing
		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] != -1 && seg[si*2+2][2] <= lval) {
			//there is a min in the right side that affects me
			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] != -1 && seg[si*2+2][1] >= lval) {
			//there is a max in the right side 
			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;

	//precautionary setting and such
	for (int i = 0; i < maxk*4; i++) {
		seg[i][0] = -1;
		seg[i][1] = -1;
		seg[i][2] = -1;
	}

	type[0] = 1;
	val[0] = 0;
	update(0, true); // i think this is good

	

	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, true, type[v]);
			update(v, true);
		}
		for (int j = 0; j < deactivate[i].size(); j++) {
			int v = deactivate[i][j];
			updatem(v, false, type[v]);
			update(v, false);
		}

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

	}

  	return;
}

Compilation message

wall.cpp: In function 'void upm(int, bool, int, int, int, int)':
wall.cpp:47:52: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if (seg[si][ind] == -1 || seg[si*2+2][ind] != -1 && seg[si*2+2][ind] < seg[si][ind]) {
                             ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:148:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < activate[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~~~~~~~
wall.cpp:153:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < deactivate[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 117752 KB Output is correct
2 Correct 116 ms 118004 KB Output is correct
3 Incorrect 115 ms 118004 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 118004 KB Output is correct
2 Correct 567 ms 133716 KB Output is correct
3 Incorrect 572 ms 133716 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 133716 KB Output is correct
2 Correct 123 ms 133716 KB Output is correct
3 Incorrect 105 ms 133716 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 133716 KB Output is correct
2 Correct 100 ms 133716 KB Output is correct
3 Incorrect 102 ms 133716 KB Output isn't correct
4 Halted 0 ms 0 KB -