oj.uz

답안 #1014084

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1014084 2024-07-04T10:34:52 Z DorostWef 벽 (IOI14_wall) C++17
0 / 100
 10 ms 23900 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;
#define F first
#define S second

const int N = 500012, SegN = (1 << 20), INF = 1e7 + 190; 
pair <int, int> seg[SegN];
vector <int> s[N], e[N]; 
pair <int, int> p[N];
int kk = 0;

void build (int v = 1, int tl = 0, int tr = kk - 1) {
	seg[v] = {INF, -INF};
	if (tl != tr) {
		int mid = (tl + tr) >> 1;
		build (v << 1, tl, mid);
		build (v << 1 | 1, mid + 1, tr);
	}
}

pair <int, int> Merge (pair <int, int> p, pair <int, int> q) {
	pair <int, int> w;
	if (q.F >= p.F)
		w = p;
	else if (q.F <= p.S) {
		w = {q.F, q.F};
	} else {
		w = {q.F, p.S};
	}
	w.S = max (w.S, q.S);
	if (w.F <= w.S)
		w = {w.S, w.S};
	return w;
}

void upd (int i, int a, int b, int v = 1, int tl = 0, int tr = kk - 1) {
	if (tl == tr) {
		seg[v].F = a;
		seg[v].S = b;
		cout << "wef" << tl << ' ' << tr << ' ' << seg[v].F << ' ' << seg[v].S << '\n';
		return;
	}
	int mid = (tl + tr) >> 1;
	if (i <= mid)
		upd (i, a, b, v << 1, tl, mid);
	else
		upd (i, a, b, v << 1 | 1, mid + 1, tr);
	seg[v] = Merge (seg[v << 1], seg[v << 1 | 1]);
	cout << "wef" << tl << ' ' << tr << ' ' << seg[v].F << ' ' << seg[v].S << '\n';
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	kk = k;
	build();
	for (int i = 0; i < k; i++) {
		s[left[i]].push_back(i);
		e[right[i]].push_back(i);
		if (op[i] == 1) {
			p[i].S = height[i];
			p[i].F = INF;
		} else {
			p[i].F = height[i];
			p[i].S = -INF;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j : s[i]) {
			cout << "s " << i << ' ' << j << ' ' << p[j].F << ' ' << p[j].S << '\n';
			upd (j, p[j].F, p[j].S);
		}
		int x = 0;
		cout << "x" << ' ' << seg[1].F << ' ' << seg[1].S << '\n';
		x = min (x, seg[1].F);
		x = max (x, seg[1].S);
		finalHeight[i] = x;
		for (int j : e[i]) {
			cout << "e " << i << ' ' << j << ' ' << INF << ' ' << -INF << '\n';
			upd (j, INF, -INF);
		}
	}
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 23896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 23900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 23896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 23900 KB Output isn't correct
2 Halted 0 ms 0 KB -