oj.uz

Submission #52388

# Submission time Handle Problem Language Result Execution time Memory
52388 2018-06-25T17:41:50 Z shoemakerjo Wall (IOI14_wall) C++14
0 / 100
 1097 ms 122384 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;
#define maxn 2000010
#define maxk 500010
const int inf = 1234567890;
int seg[maxn*4];
int cmin[maxn*4], cmax[maxn*4];

int N, K;

void delaze(int ss, int se, int si) {
	
	seg[si] = max(seg[si], cmax[si]);
	seg[si] = min(seg[si], cmin[si]);

	if (ss != se) {
		for (int d = 1; d <= 2; d++) {
			int pos = 2*si+d;
			int nmin = cmin[si];
			int nmax = cmax[si];
			if (nmin <= cmax[pos]) {
				cmax[pos] = nmax;
				cmin[pos] = nmin;
				continue;
			}
			if (nmax >= cmin[pos]) {
				cmin[pos] = nmin;
				cmax[pos] = nmax;
				continue;
			}
			if (nmin <= cmin[pos]) {
				cmin[pos] = nmin;
			}
			if (nmax >= cmax[pos]) {
				cmax[pos] = nmax;
			}
		}
	}

	cmin[si] = inf;
	cmax[si] = -1;
}


void up(int us, int ue, int nmin, int nmax, int ss, int se, int si) {
	delaze(ss, se, si);
	if (us > ue || ss > se || us > se || ue < ss) return;
	if (us <= ss && se <= ue) {
		cmin[si] = nmin;
		cmax[si] = nmax;
		delaze(ss, se, si);
		return;
	}
	int mid = (ss+se)/2;
	up(us, ue, nmin, nmax, ss, mid, si*2+1);
	up(us, ue, nmin, nmax, mid+1, se, si*2+2);

}

void update(int us, int ue, int nmin, int nmax) {
	up(us, ue, nmin, nmax, 0, N-1, 0);
}

int qu(int spot, int ss, int se, int si) {
	delaze(ss, se, si);
	if (ss == se) return seg[si];
	int mid = (ss+se)/2;
	if (spot <= mid) return qu(spot, ss, mid, si*2+1);
	return qu(spot, mid+1, se, si*2+2);
}

int query(int spot) {
	return qu(spot, 0, N-1, 0);
}

void buildWall(int n, int k, int op[], int left[], int right[], 
		int height[], int finalHeight[]){
	fill(seg, seg+maxn*4, 0);
	fill(cmax, cmax+maxn*4, -1);
	fill(cmin, cmin+maxn*4, inf);
	N = n;
	K = k;

	//do the queries
	for (int i = 0; i < k; i++) {
		if (op[i] == 1) {
			//max operation
			update(left[i], right[i], inf, height[i]);
		}
		else {
			//min operation
			update(left[i], right[i], height[i], -1);
		}
	}
	for (int i = 0; i  < n; i++) {
		finalHeight[i] = query(i);
	}
	return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 94200 KB Output is correct
2 Correct 76 ms 94448 KB Output is correct
3 Incorrect 75 ms 94572 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 94728 KB Output is correct
2 Correct 273 ms 108536 KB Output is correct
3 Correct 414 ms 108536 KB Output is correct
4 Incorrect 1097 ms 122384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 122384 KB Output is correct
2 Correct 76 ms 122384 KB Output is correct
3 Incorrect 77 ms 122384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 122384 KB Output is correct
2 Correct 77 ms 122384 KB Output is correct
3 Incorrect 74 ms 122384 KB Output isn't correct
4 Halted 0 ms 0 KB -