oj.uz

Submission #879631

# Submission time Handle Problem Language Result Execution time Memory
879631 2023-11-27T18:58:11 Z aykhn Wall (IOI14_wall) C++17
100 / 100
 789 ms 67156 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

int N;
int ans[2000000];

struct SegTree
{
	int sz;
	vector<pair<int, int>> st;
	void init(int n)
	{
		sz = 1;
		while (sz < n) sz <<= 1;
		st.assign(sz << 1, {-1, 0});
	}
	void build(int l, int r, int x)
	{
		if (l + 1 == r)
		{
			st[x] = {0, 0};
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, 2*x + 1);
		build(mid, r, 2*x + 2);
		return;
	}
	void relax(int l, int r, int x)
	{
		if (l + 1 == r) return;
		int l1 = st[x].first;
		int r1 = st[x].second;
		int l2 = st[2*x + 1].first;
		int r2 = st[2*x + 1].second;
		if (l1 >= r2) st[2*x + 1] = {l1, l1};
		else if (r1 <= l2) st[2*x + 1] = {r1, r1};
		else st[2*x + 1] = {max(l1, l2), min(r1, r2)};
		l2 = st[2*x + 2].first, r2 = st[2*x + 2].second;
		if (l1 >= r2) st[2*x + 2] = {l1, l1};
		else if (r1 <= l2) st[2*x + 2] = {r1, r1};
		else st[2*x + 2] = {max(l1, l2), min(r1, r2)};
		st[x] = {0, 1e5};
	}
	void make(int l, int r, int x, int lx, int rx, int t, int val)
	{
		relax(l, r, x);
		if (l >= rx || r <= lx) return;
		if (l >= lx && r <= rx)
		{
			if (l + 1 == r)
			{
				if (t == 1) st[x] = {max(val, st[x].first), max(val, st[x].first)};
				else st[x] = {min(val, st[x].first), min(val, st[x].first)};
				return;
			}
			if (t == 1) st[x] = {val, 1e5};
			else st[x] = {0, val};
			relax(l, r, x);
			return;
		}
		int mid = (l + r) >> 1;
		make(l, mid, 2*x + 1, lx, rx, t, val);
		make(mid, r, 2*x + 2, lx, rx, t, val);
		return;
	}
	void final(int l, int r, int x)
	{
		if (l + 1 == r) 
		{
			if (l < N) ans[l] = st[x].first;
			return;
		}
		relax(l, r, x);
		int mid = (l + r) >> 1;
		final(l, mid, 2*x + 1);
		final(mid, r, 2*x + 2);
		return;
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	SegTree st;
	N = n;
	st.init(n);
	for (int q = 0; q < k; q++)
	{
		int t = op[q];
		int lx = left[q];
		int rx = right[q];
		int val = height[q];
		st.make(0, st.sz, 0, lx, rx + 1, t, val);
	}
	st.final(0, st.sz, 0);
	for (int i = 0; i < n; i++)
	{
		finalHeight[i] = max(0, ans[i]);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 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 112 ms 13880 KB Output is correct
3 Correct 132 ms 8016 KB Output is correct
4 Correct 373 ms 22492 KB Output is correct
5 Correct 251 ms 23040 KB Output is correct
6 Correct 236 ms 21664 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 4 ms 856 KB Output is correct
6 Correct 4 ms 856 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 119 ms 14044 KB Output is correct
9 Correct 148 ms 8040 KB Output is correct
10 Correct 368 ms 22464 KB Output is correct
11 Correct 239 ms 22840 KB Output is correct
12 Correct 228 ms 21472 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 113 ms 13908 KB Output is correct
15 Correct 29 ms 2132 KB Output is correct
16 Correct 506 ms 22356 KB Output is correct
17 Correct 244 ms 21844 KB Output is correct
18 Correct 241 ms 21852 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 912 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 122 ms 13976 KB Output is correct
9 Correct 132 ms 8056 KB Output is correct
10 Correct 370 ms 22492 KB Output is correct
11 Correct 235 ms 23084 KB Output is correct
12 Correct 253 ms 21216 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 117 ms 13916 KB Output is correct
15 Correct 28 ms 2128 KB Output is correct
16 Correct 649 ms 22492 KB Output is correct
17 Correct 263 ms 21912 KB Output is correct
18 Correct 257 ms 21916 KB Output is correct
19 Correct 559 ms 67156 KB Output is correct
20 Correct 557 ms 67084 KB Output is correct
21 Correct 789 ms 67156 KB Output is correct
22 Correct 551 ms 67140 KB Output is correct
23 Correct 529 ms 67152 KB Output is correct
24 Correct 580 ms 66972 KB Output is correct
25 Correct 545 ms 67156 KB Output is correct
26 Correct 564 ms 67152 KB Output is correct
27 Correct 556 ms 67152 KB Output is correct
28 Correct 542 ms 67024 KB Output is correct
29 Correct 533 ms 67156 KB Output is correct
30 Correct 619 ms 67152 KB Output is correct