oj.uz

Submission #52399

# Submission time Handle Problem Language Result Execution time Memory
52399 2018-06-25T18:34:56 Z shoemakerjo Wall (IOI14_wall) C++14
100 / 100
 1966 ms 393216 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;
#define maxn 2000010
#define ll long long
#define maxk 500010
const ll inf = 12345678901234567LL;
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) {

		ll nmin = cmin[si];
		ll nmax = cmax[si];

		for (int d = 1; d <= 2; d++) {
			int pos = 2*si+d;

			if (nmin <= cmax[pos]) {
				cmax[pos] = nmin;
				cmin[pos] = nmin;
				continue;
			}
			if (nmax >= cmin[pos]) {
				cmin[pos] = nmax;
				cmax[pos] = nmax;
				continue;
			}
			if (nmin <= cmin[pos]) { //new thing is more effective, order should not matter here
				cmin[pos] = nmin;
			}
			if (nmax >= cmax[pos]) { //new thing is more effective, preliminary operations affect nothing
				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; //direct assign b/c we know it is delazed
		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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 188224 KB Output is correct
2 Correct 151 ms 188320 KB Output is correct
3 Correct 145 ms 188320 KB Output is correct
4 Correct 139 ms 188496 KB Output is correct
5 Correct 141 ms 188728 KB Output is correct
6 Correct 140 ms 188980 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 188980 KB Output is correct
2 Correct 300 ms 196468 KB Output is correct
3 Correct 471 ms 196468 KB Output is correct
4 Correct 1311 ms 197188 KB Output is correct
5 Correct 642 ms 207856 KB Output is correct
6 Correct 663 ms 216520 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 216520 KB Output is correct
2 Correct 136 ms 216520 KB Output is correct
3 Correct 131 ms 216520 KB Output is correct
4 Correct 139 ms 216520 KB Output is correct
5 Correct 143 ms 216520 KB Output is correct
6 Correct 141 ms 216520 KB Output is correct
7 Correct 135 ms 216520 KB Output is correct
8 Correct 303 ms 221484 KB Output is correct
9 Correct 494 ms 221484 KB Output is correct
10 Correct 1213 ms 235676 KB Output is correct
11 Correct 615 ms 246312 KB Output is correct
12 Correct 631 ms 254852 KB Output is correct
13 Correct 140 ms 254852 KB Output is correct
14 Correct 358 ms 259436 KB Output is correct
15 Correct 209 ms 259436 KB Output is correct
16 Correct 1428 ms 270476 KB Output is correct
17 Correct 643 ms 279648 KB Output is correct
18 Correct 618 ms 288636 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 288636 KB Output is correct
2 Correct 131 ms 288636 KB Output is correct
3 Correct 131 ms 288636 KB Output is correct
4 Correct 140 ms 288636 KB Output is correct
5 Correct 137 ms 288636 KB Output is correct
6 Correct 137 ms 288636 KB Output is correct
7 Correct 128 ms 288636 KB Output is correct
8 Correct 309 ms 293860 KB Output is correct
9 Correct 484 ms 293860 KB Output is correct
10 Correct 1296 ms 307920 KB Output is correct
11 Correct 624 ms 318704 KB Output is correct
12 Correct 690 ms 327176 KB Output is correct
13 Correct 131 ms 327176 KB Output is correct
14 Correct 313 ms 331844 KB Output is correct
15 Correct 196 ms 331844 KB Output is correct
16 Correct 1474 ms 342888 KB Output is correct
17 Correct 653 ms 352016 KB Output is correct
18 Correct 684 ms 361044 KB Output is correct
19 Correct 1940 ms 388488 KB Output is correct
20 Correct 1907 ms 393216 KB Output is correct
21 Correct 1748 ms 393216 KB Output is correct
22 Correct 1957 ms 393216 KB Output is correct
23 Correct 1966 ms 393216 KB Output is correct
24 Correct 1822 ms 393216 KB Output is correct
25 Correct 1762 ms 393216 KB Output is correct
26 Correct 1743 ms 393216 KB Output is correct
27 Correct 1741 ms 393216 KB Output is correct
28 Correct 1747 ms 393216 KB Output is correct
29 Correct 1884 ms 393216 KB Output is correct
30 Correct 1908 ms 393216 KB Output is correct