oj.uz

Submission #416849

# Submission time Handle Problem Language Result Execution time Memory
416849 2021-06-03T04:47:07 Z DEQK Wall (IOI14_wall) C++17
100 / 100
 995 ms 100832 KB 
#include <wall.h>
#include <bits/stdc++.h>

#define ll long long
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
const int N = 2e6 + 11;
int kp[N * 4];
int mn[N * 4], mx[N * 4];
void push(int u) {
	if(kp[u] == -1) return;
	mn[ls] = mn[rs] = kp[u];
	mx[ls] = mx[rs] = kp[u];
	kp[ls] = kp[rs] = kp[u];
	kp[u] = -1;
}
void add(int ql,int qr,int x,int u,int l,int r) {
	if(ql > r || l > qr || mn[u] >= x) return;
	if(ql <= l && r <= qr) {
		if(mx[u] <= x) {
			mn[u] = mx[u] = x;
			kp[u] = x;
			return;
		}
	}
	push(u);
	int m = l + r >> 1;
	add(ql, qr, x, ls, l, m);
	add(ql, qr, x, rs, m + 1, r);
	mn[u] = min(mn[ls], mn[rs]);
	mx[u] = max(mx[ls], mx[rs]);
}
void del(int ql,int qr,int x,int u,int l,int r) {
	if(ql > r || l > qr || mx[u] <= x) return;
	if(ql <= l && r <= qr) {
		if(mn[u] >= x) {
			mn[u] = mx[u] = x;
			kp[u] = x;
			return;
		}
	}
	push(u);
	int m = l + r >> 1;
	del(ql, qr, x, ls, l, m);
	del(ql, qr, x, rs, m + 1, r);
	mn[u] = min(mn[ls], mn[rs]);
	mx[u] = max(mx[ls], mx[rs]);
}
int get(int p,int u,int l,int r) {
	if(l == r) {
		return mn[u];
	}
	push(u);
	int m = l + r >> 1;
	if(p <= m) return get(p, ls, l, m);
	else return get(p, rs, m + 1, r);
}
void buildWall(int n,int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	memset(kp, -1, sizeof(kp));
	for(int i = 0; i < k; i++) {
		int l = left[i], r = right[i], type = op[i], x = height[i];
		if(type == 1) {
			add(l, r, x, 1, 0, n - 1);
		} else {
			del(l, r, x, 1, 0, n - 1);
		}
	}	
	for(int i = 0; i < n; i++) {
		finalHeight[i] = get(i, 1, 0, n - 1);
	}
}

Compilation message

wall.cpp: In function 'void add(int, int, int, int, int, int)':
wall.cpp:28:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |  int m = l + r >> 1;
      |          ~~^~~
wall.cpp: In function 'void del(int, int, int, int, int, int)':
wall.cpp:44:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |  int m = l + r >> 1;
      |          ~~^~~
wall.cpp: In function 'int get(int, int, int, int)':
wall.cpp:55:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |  int m = l + r >> 1;
      |          ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31616 KB Output is correct
2 Correct 15 ms 31748 KB Output is correct
3 Correct 15 ms 31692 KB Output is correct
4 Correct 24 ms 32088 KB Output is correct
5 Correct 19 ms 32080 KB Output is correct
6 Correct 21 ms 32012 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31564 KB Output is correct
2 Correct 173 ms 45136 KB Output is correct
3 Correct 96 ms 39184 KB Output is correct
4 Correct 217 ms 51668 KB Output is correct
5 Correct 233 ms 52808 KB Output is correct
6 Correct 257 ms 51140 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31564 KB Output is correct
2 Correct 15 ms 31700 KB Output is correct
3 Correct 14 ms 31692 KB Output is correct
4 Correct 20 ms 32204 KB Output is correct
5 Correct 19 ms 32012 KB Output is correct
6 Correct 19 ms 32072 KB Output is correct
7 Correct 15 ms 31540 KB Output is correct
8 Correct 201 ms 45260 KB Output is correct
9 Correct 99 ms 39240 KB Output is correct
10 Correct 216 ms 51636 KB Output is correct
11 Correct 235 ms 52692 KB Output is correct
12 Correct 304 ms 51184 KB Output is correct
13 Correct 13 ms 31564 KB Output is correct
14 Correct 181 ms 45176 KB Output is correct
15 Correct 47 ms 33304 KB Output is correct
16 Correct 533 ms 51928 KB Output is correct
17 Correct 354 ms 51296 KB Output is correct
18 Correct 361 ms 51408 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31564 KB Output is correct
2 Correct 15 ms 31724 KB Output is correct
3 Correct 14 ms 31596 KB Output is correct
4 Correct 19 ms 32056 KB Output is correct
5 Correct 20 ms 32052 KB Output is correct
6 Correct 23 ms 32024 KB Output is correct
7 Correct 16 ms 31604 KB Output is correct
8 Correct 184 ms 45152 KB Output is correct
9 Correct 96 ms 39236 KB Output is correct
10 Correct 218 ms 51584 KB Output is correct
11 Correct 256 ms 52736 KB Output is correct
12 Correct 288 ms 51168 KB Output is correct
13 Correct 15 ms 31516 KB Output is correct
14 Correct 183 ms 45200 KB Output is correct
15 Correct 44 ms 33228 KB Output is correct
16 Correct 528 ms 51868 KB Output is correct
17 Correct 370 ms 51316 KB Output is correct
18 Correct 360 ms 51308 KB Output is correct
19 Correct 995 ms 100832 KB Output is correct
20 Correct 943 ms 98396 KB Output is correct
21 Correct 952 ms 100748 KB Output is correct
22 Correct 974 ms 98356 KB Output is correct
23 Correct 953 ms 98368 KB Output is correct
24 Correct 943 ms 98392 KB Output is correct
25 Correct 958 ms 98208 KB Output is correct
26 Correct 953 ms 100772 KB Output is correct
27 Correct 954 ms 100764 KB Output is correct
28 Correct 957 ms 98388 KB Output is correct
29 Correct 937 ms 98220 KB Output is correct
30 Correct 943 ms 98336 KB Output is correct