oj.uz

답안 #230790

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
230790 2020-05-11T18:28:39 Z cheissmart 벽 (IOI14_wall) C++14
100 / 100
 742 ms 62224 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(v) (v).beign(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

const int N = 2000006, INF = 1e9 + 7;

struct S {
	int ub, lb;
} t[N * 4];

void init(int v, int tl, int tr) {
	t[v].ub = INF;
	t[v].lb = 0;
	if(tr - tl == 1) return;
	int tm = (tl + tr) / 2;
	init(v*2, tl, tm);
	init(v*2+1, tm, tr);
}

void put_tag(int v, int op, int h) {
	if(op == 1) { // lb
		t[v].lb = max(t[v].lb, h);
		if(t[v].lb >= t[v].ub) t[v].ub = t[v].lb;
	} else { // rb
		t[v].ub = min(t[v].ub, h);
		if(t[v].lb >= t[v].ub) t[v].lb = t[v].ub;
	}
}

void push(int v) {
	put_tag(v*2, 1, t[v].lb);
	put_tag(v*2, 2, t[v].ub);
	put_tag(v*2+1, 1, t[v].lb);
	put_tag(v*2+1, 2, t[v].ub);
	t[v].lb = 0, t[v].ub = INF;
}

void upd(int l, int r, int op, int h, int v, int tl, int tr) {
	if(l >= r) return;
	if(l == tl && r == tr) {
		put_tag(v, op, h);
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	upd(l, min(r, tm), op, h, v*2, tl, tm);
	upd(max(l, tm), r, op, h, v*2+1, tm, tr);
}

void build_ans(int v, int tl, int tr, int* ans) {
	if(tr - tl == 1) {
		ans[tl] = t[v].lb;
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	build_ans(v*2, tl, tm, ans);
	build_ans(v*2 + 1, tm, tr, ans);
}

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

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 12 ms 896 KB Output is correct
5 Correct 10 ms 896 KB Output is correct
6 Correct 10 ms 896 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 172 ms 11004 KB Output is correct
3 Correct 177 ms 7032 KB Output is correct
4 Correct 473 ms 13944 KB Output is correct
5 Correct 314 ms 14420 KB Output is correct
6 Correct 317 ms 14328 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 11 ms 896 KB Output is correct
5 Correct 9 ms 896 KB Output is correct
6 Correct 9 ms 896 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 175 ms 11044 KB Output is correct
9 Correct 175 ms 7032 KB Output is correct
10 Correct 482 ms 13944 KB Output is correct
11 Correct 322 ms 14456 KB Output is correct
12 Correct 306 ms 14456 KB Output is correct
13 Correct 4 ms 256 KB Output is correct
14 Correct 172 ms 11256 KB Output is correct
15 Correct 39 ms 2040 KB Output is correct
16 Correct 611 ms 14300 KB Output is correct
17 Correct 317 ms 14076 KB Output is correct
18 Correct 324 ms 14200 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 11 ms 896 KB Output is correct
5 Correct 9 ms 896 KB Output is correct
6 Correct 9 ms 896 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 180 ms 11000 KB Output is correct
9 Correct 178 ms 7160 KB Output is correct
10 Correct 486 ms 13992 KB Output is correct
11 Correct 330 ms 14456 KB Output is correct
12 Correct 307 ms 14456 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 173 ms 11256 KB Output is correct
15 Correct 39 ms 2040 KB Output is correct
16 Correct 604 ms 14208 KB Output is correct
17 Correct 320 ms 14328 KB Output is correct
18 Correct 321 ms 14200 KB Output is correct
19 Correct 741 ms 62224 KB Output is correct
20 Correct 713 ms 59620 KB Output is correct
21 Correct 739 ms 61920 KB Output is correct
22 Correct 742 ms 59472 KB Output is correct
23 Correct 721 ms 59492 KB Output is correct
24 Correct 706 ms 59552 KB Output is correct
25 Correct 692 ms 59384 KB Output is correct
26 Correct 712 ms 61944 KB Output is correct
27 Correct 723 ms 61948 KB Output is correct
28 Correct 715 ms 59384 KB Output is correct
29 Correct 707 ms 59396 KB Output is correct
30 Correct 707 ms 59340 KB Output is correct