oj.uz

Submission #1079384

# Submission time Handle Problem Language Result Execution time Memory
1079384 2024-08-28T13:45:47 Z vjudge1 Wall (IOI14_wall) C++17
100 / 100
 578 ms 110420 KB 
#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e6 + 5, inf = 1e9 + 5;
int mi[maxn << 2], mx[maxn << 2], N, res[maxn];
pair<int, int> lazy[maxn << 2];

void pull_inc(int id, int k) {
	mi[id] = max(mi[id], k);
	mx[id] = max(mx[id], k);
	lazy[id].first = max(lazy[id].first, k);
	lazy[id].second = max(lazy[id].second, k);
}

void pull_dec(int id, int k) {
	mi[id] = min(mi[id], k);
	mx[id] = min(mx[id], k);
	lazy[id].first = min(lazy[id].first, k);
	lazy[id].second = min(lazy[id].second, k);
}

void shift(int id){
    if(lazy[id].first != -inf){
        pull_inc(id << 1, lazy[id].first);
        pull_inc(id << 1 | 1, lazy[id].first);
    }
    if(lazy[id].second != inf){
        pull_dec(id << 1, lazy[id].second);
        pull_dec(id << 1 | 1, lazy[id].second);
    }
    lazy[id] = {-inf, inf};
}

void upd(int L, int R, int k, int t, int id = 1, int tl = 0, int tr = N - 1) {
	if (L > tr || R < tl) return;
	if (L <= tl && R >= tr) {
		if (t == 1) pull_inc(id, k);
		else pull_dec(id, k);
		return;
	}
	shift(id);
	upd(L, R, k, t, id << 1, tl, (tl + tr) >> 1);
	upd(L, R, k, t, id << 1 | 1, ((tl + tr) >> 1) + 1, tr);
	mi[id] = min(mi[id << 1], mi[id << 1 | 1]);
	mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
}

void get(int id = 1, int tl = 0, int tr = N - 1) {
	if (tl == tr) { res[tl] = mi[id]; return; }
	shift(id);
	get(id << 1, tl, (tl + tr) >> 1);
	get(id << 1 | 1, ((tl + tr) >> 1) + 1, tr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	N = n;
	for (int i = 0; i < k; i++) upd(left[i], right[i], height[i], op[i]);
	get();
	for (int i = 0; i < N; i++) finalHeight[i] = res[i];
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 4 ms 1156 KB Output is correct
6 Correct 4 ms 1156 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 80 ms 13932 KB Output is correct
3 Correct 138 ms 8532 KB Output is correct
4 Correct 400 ms 22868 KB Output is correct
5 Correct 210 ms 23892 KB Output is correct
6 Correct 202 ms 22352 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 84 ms 14116 KB Output is correct
9 Correct 135 ms 8528 KB Output is correct
10 Correct 398 ms 22804 KB Output is correct
11 Correct 206 ms 23916 KB Output is correct
12 Correct 206 ms 22488 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 85 ms 13908 KB Output is correct
15 Correct 24 ms 2640 KB Output is correct
16 Correct 502 ms 23120 KB Output is correct
17 Correct 206 ms 22464 KB Output is correct
18 Correct 211 ms 22612 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 1116 KB Output is correct
5 Correct 3 ms 1156 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 86 ms 14032 KB Output is correct
9 Correct 139 ms 8532 KB Output is correct
10 Correct 391 ms 23008 KB Output is correct
11 Correct 205 ms 23964 KB Output is correct
12 Correct 207 ms 22476 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 105 ms 13908 KB Output is correct
15 Correct 25 ms 2644 KB Output is correct
16 Correct 483 ms 23048 KB Output is correct
17 Correct 220 ms 22540 KB Output is correct
18 Correct 210 ms 22608 KB Output is correct
19 Correct 516 ms 110328 KB Output is correct
20 Correct 510 ms 108036 KB Output is correct
21 Correct 509 ms 110420 KB Output is correct
22 Correct 505 ms 108036 KB Output is correct
23 Correct 502 ms 107840 KB Output is correct
24 Correct 502 ms 107860 KB Output is correct
25 Correct 519 ms 107856 KB Output is correct
26 Correct 506 ms 110164 KB Output is correct
27 Correct 512 ms 110164 KB Output is correct
28 Correct 576 ms 107600 KB Output is correct
29 Correct 578 ms 107700 KB Output is correct
30 Correct 573 ms 107740 KB Output is correct