oj.uz

Submission #52392

# Submission time Handle Problem Language Result Execution time Memory
52392 2018-06-25T17:47:37 Z shoemakerjo Wall (IOI14_wall) C++14
0 / 100
 1300 ms 196820 KB 
#include "wall.h"
#include <bits/stdc++.h>

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

int N, K;

//maintain cmax[si] <= cmin[si]
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;
			ll nmin = cmin[si];
			ll 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; //reset the values
	cmax[si] = -1;
}


void up(int us, int ue, ll nmin, ll 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, ll nmin, ll 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 150 ms 188280 KB Output is correct
2 Correct 151 ms 188280 KB Output is correct
3 Incorrect 138 ms 188320 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 188320 KB Output is correct
2 Correct 321 ms 196380 KB Output is correct
3 Correct 480 ms 196380 KB Output is correct
4 Incorrect 1300 ms 196820 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 196820 KB Output is correct
2 Correct 141 ms 196820 KB Output is correct
3 Incorrect 158 ms 196820 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 196820 KB Output is correct
2 Correct 146 ms 196820 KB Output is correct
3 Incorrect 139 ms 196820 KB Output isn't correct
4 Halted 0 ms 0 KB -