oj.uz

답안 #784000

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
784000 2023-07-15T14:10:08 Z acatmeowmeow 벽 (IOI14_wall) C++11
61 / 100
 578 ms 144724 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6;
pair<int, int> tree[4*N + 5], lazy[4*N + 5];

pair<int, int> combine(pair<int, int>f, pair<int, int>se) {
	int a = max(f.first, se.first), b = min(f.second, se.second);
	if (b < a) {
		if (se.second < f.first) return pair<int, int>(se.second, se.second);
		else return pair<int, int>(se.first, se.first);
	} else {
		return pair<int, int>(a, b);
	}
}

void push(int v) {
	tree[v*2] = combine(tree[v*2], lazy[v]), tree[v*2 + 1] = combine(tree[v*2 + 1], lazy[v]);
	lazy[v*2] = combine(lazy[v*2], lazy[v]), lazy[v*2 + 1] = combine(lazy[v*2 + 1], lazy[v]);
	lazy[v] = {-1e9, 1e9};
}

void update(int v, int tl, int tr, int l, int r, pair<int, int> x) {
	if (l > r) return;
	else if (tl == l && tr == r) tree[v] = combine(tree[v], x), lazy[v] = combine(lazy[v], x);
	else {
		push(v);
		int tm = (tl + tr)/2;
		update(v*2, tl, tm, l, min(tm, r), x);
		update(v*2 + 1, tm + 1, tr, max(l, tm + 1), r, x);
	}
}

pair<int, int> query(int v, int tl, int tr, int k) {
	if (tl == tr) return tree[v];
	else {
		push(v);
		int tm = (tl + tr)/2;
		if (k <= tm) return query(v*2, tl, tm, k);
		else return query(v*2 + 1, tm + 1, tr, k);
	}
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for (int i = 1; i <= 4*N; i++) tree[i] = lazy[i] = {-1e9, 1e9};
	for (int i = 0; i < k; i++) {
		int l = left[i], r = right[i], type = op[i], h = height[i];
		if (type == 1) {
			update(1, 0, n - 1, l, r, {h, 1e9});
		} else {
			update(1, 0, n - 1, l, r, {-1e9, h});
		}
	}
	for (int i = 0; i < n; i++) {
		pair<int, int> ans = query(1, 0, n - 1, i);
		//cout << ans.first << " " << ans.second << '\n';
		finalHeight[i] = max(0, ans.first);
	}
}

/*int main()
{
  int n;
  int k;

  int i, j;  
  int status = 0;

	cin >> n >> k;

  int* op = (int*)calloc(sizeof(int), k);
  int* left = (int*)calloc(sizeof(int), k);
  int* right = (int*)calloc(sizeof(int), k);
  int* height = (int*)calloc(sizeof(int), k);
  int* finalHeight = (int*)calloc(sizeof(int), n);

  for (i = 0; i < k; i++){
	  cin >> op[i] >> left[i] >> right[i] >> height[i];
 //   status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
   // assert(status == 4);
  }

  buildWall(n, k, op, left, right, height, finalHeight);

  for (j = 0; j < n; j++)
    //printf("%d\n", finalHeight[j]);
	cout << finalHeight[j] << '\n';
  
  return 0;
}*/

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 62872 KB Output is correct
2 Correct 29 ms 62928 KB Output is correct
3 Correct 28 ms 62928 KB Output is correct
4 Correct 36 ms 63112 KB Output is correct
5 Correct 34 ms 63104 KB Output is correct
6 Correct 34 ms 63068 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 62888 KB Output is correct
2 Correct 125 ms 71332 KB Output is correct
3 Correct 169 ms 66900 KB Output is correct
4 Correct 428 ms 71968 KB Output is correct
5 Correct 267 ms 73236 KB Output is correct
6 Correct 266 ms 73272 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 62804 KB Output is correct
2 Correct 29 ms 63000 KB Output is correct
3 Correct 31 ms 62924 KB Output is correct
4 Correct 39 ms 63140 KB Output is correct
5 Correct 33 ms 63068 KB Output is correct
6 Correct 33 ms 63156 KB Output is correct
7 Correct 29 ms 62796 KB Output is correct
8 Correct 140 ms 71368 KB Output is correct
9 Correct 175 ms 66872 KB Output is correct
10 Correct 433 ms 71940 KB Output is correct
11 Correct 267 ms 73284 KB Output is correct
12 Correct 271 ms 73244 KB Output is correct
13 Correct 27 ms 62804 KB Output is correct
14 Correct 129 ms 72136 KB Output is correct
15 Correct 60 ms 64036 KB Output is correct
16 Correct 575 ms 73036 KB Output is correct
17 Correct 326 ms 72952 KB Output is correct
18 Correct 278 ms 72980 KB Output is correct

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 62900 KB Output is correct
2 Correct 29 ms 62992 KB Output is correct
3 Correct 29 ms 62904 KB Output is correct
4 Correct 35 ms 63084 KB Output is correct
5 Correct 33 ms 63140 KB Output is correct
6 Correct 33 ms 63180 KB Output is correct
7 Correct 29 ms 62900 KB Output is correct
8 Correct 137 ms 71360 KB Output is correct
9 Correct 177 ms 66824 KB Output is correct
10 Correct 429 ms 71884 KB Output is correct
11 Correct 274 ms 73220 KB Output is correct
12 Correct 269 ms 73208 KB Output is correct
13 Correct 27 ms 62804 KB Output is correct
14 Correct 128 ms 72076 KB Output is correct
15 Correct 67 ms 64092 KB Output is correct
16 Correct 578 ms 72996 KB Output is correct
17 Correct 280 ms 72932 KB Output is correct
18 Correct 317 ms 72932 KB Output is correct
19 Runtime error 194 ms 144724 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -