oj.uz

Submission #541767

# Submission time Handle Problem Language Result Execution time Memory
541767 2022-03-24T11:07:59 Z starchan Wall (IOI14_wall) C++17
100 / 100
 1113 ms 144064 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF 1e6
#define zero (int)0
#define MX (int)3e5+5
#define LMX (int)1e7
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL);
const int mod = 1e9+7; //may fixer to that 99.. number.
struct fixer
{
	int down, up;
};
fixer crate(const int &a, const int &b)
{
	fixer ok;
	ok.down = a;
	ok.up = b;
	assert(a<=b);
	return ok;
}
fixer identity = crate(-INF, INF);
fixer superimpose(const fixer &c1, const fixer &c2)
{
	fixer c3;
	c3.down = max(c1.down, c2.down);
	c3.up = min(c1.up, c2.up);
	if(c3.up >= c3.down)
		return c3;
	if(c3.down == c2.down)
		return crate(c1.up, c1.up);
	else
		return crate(c1.down, c1.down);
}
struct segment_tree
{
	vector<int> tree;
	vector<fixer> lazy;
	void init()
	{
		tree.assign(LMX, 0);
		lazy.assign(LMX, identity);
		return;
	}
	void apply(int id, fixer c)
	{
		if(tree[id] <= c.down)
			tree[id] = c.down;
		if(tree[id] >= c.up)
			tree[id] = c.up;
		lazy[id] = superimpose(c, lazy[id]);
		return;
	}
	void push(int id)
	{
		apply(2*id, lazy[id]);
		apply(2*id+1, lazy[id]);
		lazy[id] = identity;
		return;
	}
	void upd(fixer place, int ql, int qr, int id, int l, int r)
	{
		if(qr < l || r < ql)
			return;
		if(ql <= l && r <= qr)
		{
			apply(id, place);
			return;
		}
		int m = (l+r)/2;
		push(id);
		upd(place, ql, qr, 2*id, l, m);
		upd(place, ql, qr, 2*id+1, m+1, r);
		return;
	}
	int val(int pos, int id, int l, int r)
	{
		int m = (l+r)/2;
		if(l==r)
			return tree[id];
		push(id);
		if(pos <= m)
			return val(pos, 2*id, l, m);
		else
			return val(pos, 2*id+1, m+1, r);
	}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	segment_tree work;
	work.init();
	for(int i = 0; i < k; i++)
	{
		if(op[i] == 1)
			work.upd(crate(height[i], INF), left[i], right[i], 1, 0, n-1);
		else
			work.upd(crate(-INF, height[i]), left[i], right[i], 1, 0, n-1);
	}
	for(int i = 0; i < n; i++)
		finalHeight[i] = work.val(i, 1, 0, n-1);
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 117708 KB Output is correct
2 Correct 45 ms 117768 KB Output is correct
3 Correct 49 ms 117696 KB Output is correct
4 Correct 52 ms 117908 KB Output is correct
5 Correct 62 ms 117864 KB Output is correct
6 Correct 54 ms 117920 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 117696 KB Output is correct
2 Correct 182 ms 131328 KB Output is correct
3 Correct 206 ms 124820 KB Output is correct
4 Correct 513 ms 135732 KB Output is correct
5 Correct 354 ms 136036 KB Output is correct
6 Correct 343 ms 134548 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 117580 KB Output is correct
2 Correct 47 ms 117800 KB Output is correct
3 Correct 49 ms 117660 KB Output is correct
4 Correct 57 ms 117896 KB Output is correct
5 Correct 50 ms 117792 KB Output is correct
6 Correct 57 ms 117884 KB Output is correct
7 Correct 46 ms 117648 KB Output is correct
8 Correct 182 ms 131244 KB Output is correct
9 Correct 228 ms 124772 KB Output is correct
10 Correct 514 ms 135560 KB Output is correct
11 Correct 362 ms 136032 KB Output is correct
12 Correct 331 ms 134544 KB Output is correct
13 Correct 47 ms 117708 KB Output is correct
14 Correct 196 ms 131348 KB Output is correct
15 Correct 81 ms 118776 KB Output is correct
16 Correct 705 ms 135564 KB Output is correct
17 Correct 381 ms 134936 KB Output is correct
18 Correct 351 ms 134984 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 117692 KB Output is correct
2 Correct 47 ms 117776 KB Output is correct
3 Correct 45 ms 117692 KB Output is correct
4 Correct 50 ms 117836 KB Output is correct
5 Correct 49 ms 117936 KB Output is correct
6 Correct 58 ms 117844 KB Output is correct
7 Correct 46 ms 117632 KB Output is correct
8 Correct 182 ms 131336 KB Output is correct
9 Correct 206 ms 124812 KB Output is correct
10 Correct 514 ms 135648 KB Output is correct
11 Correct 363 ms 136112 KB Output is correct
12 Correct 342 ms 134540 KB Output is correct
13 Correct 47 ms 117684 KB Output is correct
14 Correct 193 ms 131276 KB Output is correct
15 Correct 87 ms 118756 KB Output is correct
16 Correct 688 ms 135564 KB Output is correct
17 Correct 362 ms 134892 KB Output is correct
18 Correct 342 ms 135004 KB Output is correct
19 Correct 1070 ms 143840 KB Output is correct
20 Correct 1048 ms 143820 KB Output is correct
21 Correct 1113 ms 143824 KB Output is correct
22 Correct 1064 ms 144064 KB Output is correct
23 Correct 1022 ms 143864 KB Output is correct
24 Correct 1020 ms 143816 KB Output is correct
25 Correct 1047 ms 143728 KB Output is correct
26 Correct 1060 ms 143816 KB Output is correct
27 Correct 1038 ms 143712 KB Output is correct
28 Correct 1032 ms 143816 KB Output is correct
29 Correct 1000 ms 143852 KB Output is correct
30 Correct 1018 ms 143820 KB Output is correct