oj.uz

Submission #369459

# Submission time Handle Problem Language Result Execution time Memory
369459 2021-02-21T17:43:13 Z pure_mem Wall (IOI14_wall) C++14
100 / 100
 850 ms 140224 KB 
#include "wall.h"
#include <utility>
#include <algorithm>

#define ll long long
#define X first
#define Y second
#define MP make_pair

using namespace std;

const int N = 2e6 + 12;
const int INF = 1e6;

pair<int, int> t[N * 4], tt[N * 4];
int fin[N];

pair<int, int> merge(pair<int, int> x, pair<int, int> y){
	if(y == MP(0, INF))
		return x;
	if(y.Y <= x.X)
		return MP(x.X, x.X);
	if(x.Y <= y.X)
		return MP(x.Y, x.Y);
	if(x.X <= y.X && y.X <= x.Y)
		x.X = y.X;
	if(x.X <= y.Y && y.Y <= x.Y)
		x.Y = y.Y;
	return x;
}

void push(int v){
	if(tt[v] == MP(0, INF))
		return;
	t[v * 2] = merge(tt[v], t[v * 2]);
	tt[v * 2] = merge(tt[v], tt[v * 2]);
	t[v * 2 + 1] = merge(tt[v], t[v * 2 + 1]);
	tt[v * 2 + 1] = merge(tt[v], tt[v * 2 + 1]);
	tt[v] = MP(0, INF); 
}

void upd(int v, int tl, int tr, int l, int r, pair<int, int> val){
	if(tl > r || l > tr)
		return;
	if(tl >= l && tr <= r){
		tt[v] = merge(val, tt[v]), t[v] = merge(val, t[v]);
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	upd(v * 2, tl, tm, l, r, val);
	upd(v * 2 + 1, tm + 1, tr, l, r, val);
}

void solve(int v, int tl, int tr){
	if(tl == tr){
		fin[tl] = t[v].X;
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	solve(v * 2, tl, tm), solve(v * 2 + 1, tm + 1, tr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i = 1;i <= n * 4;i++)
		tt[i] = MP(0, INF);
	for(int i = 0;i < k;i++){
		if(op[i] == 1){
			upd(1, 1, n, left[i] + 1, right[i] + 1, MP(height[i], INF));
		}
		else{
		    upd(1, 1, n, left[i] + 1, right[i] + 1, MP(0, height[i]));
		}
	}
	solve(1, 1, n);
	for(int i = 1;i <= n;i++)
		finalHeight[i - 1] = fin[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 8 ms 1260 KB Output is correct
5 Correct 6 ms 1260 KB Output is correct
6 Correct 6 ms 1280 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 191 ms 13932 KB Output is correct
3 Correct 251 ms 8940 KB Output is correct
4 Correct 779 ms 23932 KB Output is correct
5 Correct 320 ms 24940 KB Output is correct
6 Correct 309 ms 23476 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 8 ms 1260 KB Output is correct
5 Correct 6 ms 1260 KB Output is correct
6 Correct 6 ms 1260 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 174 ms 14060 KB Output is correct
9 Correct 269 ms 8708 KB Output is correct
10 Correct 777 ms 24092 KB Output is correct
11 Correct 323 ms 25068 KB Output is correct
12 Correct 304 ms 23660 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 178 ms 13932 KB Output is correct
15 Correct 44 ms 2816 KB Output is correct
16 Correct 807 ms 24172 KB Output is correct
17 Correct 318 ms 23808 KB Output is correct
18 Correct 326 ms 23788 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 9 ms 1260 KB Output is correct
5 Correct 6 ms 1260 KB Output is correct
6 Correct 6 ms 1260 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 185 ms 14120 KB Output is correct
9 Correct 250 ms 8684 KB Output is correct
10 Correct 755 ms 23964 KB Output is correct
11 Correct 319 ms 25068 KB Output is correct
12 Correct 306 ms 23404 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 180 ms 13932 KB Output is correct
15 Correct 43 ms 2668 KB Output is correct
16 Correct 809 ms 24300 KB Output is correct
17 Correct 318 ms 23660 KB Output is correct
18 Correct 367 ms 23660 KB Output is correct
19 Correct 836 ms 140076 KB Output is correct
20 Correct 811 ms 137584 KB Output is correct
21 Correct 850 ms 140112 KB Output is correct
22 Correct 834 ms 137784 KB Output is correct
23 Correct 797 ms 137572 KB Output is correct
24 Correct 817 ms 137704 KB Output is correct
25 Correct 805 ms 137708 KB Output is correct
26 Correct 810 ms 140000 KB Output is correct
27 Correct 837 ms 140224 KB Output is correct
28 Correct 843 ms 137752 KB Output is correct
29 Correct 805 ms 137580 KB Output is correct
30 Correct 802 ms 137580 KB Output is correct