oj.uz

답안 #784013

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

using namespace std;

struct node {
	pair<int, int> v = {-1e9, 1e9}, lazy = {-1e9, 1e9};		
	node* lef = nullptr, *rig = nullptr;

	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() {
		if (!lef) lef = new node(), rig = new node();
		lef->v = combine(lef->v, lazy), rig->v = combine(rig->v, lazy);
		lef->lazy = combine(lef->lazy, lazy), rig->lazy = combine(rig->lazy, lazy);
		lazy = {-1e9, 1e9};
	}

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

	pair<int, int> query(int tl, int tr, int k) {
		if (tl == tr) return v;
		else {
			push();
			int tm = (tl + tr)/2;
			if (k <= tm) return lef->query(tl, tm, k);
			else return rig->query(tm + 1, tr, k);
		}
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	node*root = new node();
	for (int i = 0; i < k; i++) {
		int type = op[i], l = left[i], r = right[i], h = height[i];
		if (type == 1) root->update(0, n - 1, l, r, {h, 1e9});
		else root->update(0, n - 1, l, r, {-1e9, h});
	}
	for (int i = 0; i < n; i++) {
		pair<int, int> ans = root->query(0, n - 1, i);
		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 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 1312 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 5 ms 1364 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 110 ms 8128 KB Output is correct
3 Correct 136 ms 5344 KB Output is correct
4 Correct 414 ms 18040 KB Output is correct
5 Correct 237 ms 18508 KB Output is correct
6 Correct 231 ms 18508 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 1296 KB Output is correct
5 Correct 6 ms 1364 KB Output is correct
6 Correct 6 ms 1364 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 113 ms 8124 KB Output is correct
9 Correct 139 ms 5336 KB Output is correct
10 Correct 412 ms 18032 KB Output is correct
11 Correct 241 ms 18532 KB Output is correct
12 Correct 226 ms 18500 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 114 ms 8084 KB Output is correct
15 Correct 33 ms 2536 KB Output is correct
16 Correct 590 ms 18288 KB Output is correct
17 Correct 243 ms 18240 KB Output is correct
18 Correct 291 ms 18236 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 7 ms 1356 KB Output is correct
5 Correct 5 ms 1404 KB Output is correct
6 Correct 7 ms 1372 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 107 ms 8092 KB Output is correct
9 Correct 135 ms 5324 KB Output is correct
10 Correct 414 ms 18104 KB Output is correct
11 Correct 239 ms 18524 KB Output is correct
12 Correct 227 ms 18560 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 113 ms 8044 KB Output is correct
15 Correct 33 ms 2508 KB Output is correct
16 Correct 657 ms 18292 KB Output is correct
17 Correct 254 ms 18252 KB Output is correct
18 Correct 241 ms 18264 KB Output is correct
19 Correct 929 ms 214092 KB Output is correct
20 Correct 946 ms 213168 KB Output is correct
21 Correct 919 ms 215720 KB Output is correct
22 Correct 915 ms 212996 KB Output is correct
23 Correct 923 ms 213044 KB Output is correct
24 Correct 953 ms 213116 KB Output is correct
25 Correct 968 ms 213044 KB Output is correct
26 Correct 925 ms 215536 KB Output is correct
27 Correct 918 ms 215632 KB Output is correct
28 Correct 926 ms 212996 KB Output is correct
29 Correct 930 ms 213044 KB Output is correct
30 Correct 977 ms 213152 KB Output is correct