oj.uz

답안 #789516

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
789516 2023-07-21T13:00:21 Z OrazB 벽 (IOI14_wall) C++14
0 / 100
 119 ms 8036 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pii pair <int, int>
#define ff first
#define ss second

const int N = 3e6;
const int inf = 1e9+7;
int NP, q, t[4*N][2], pos[4*N];
pii lazy[4*N];

// void F(int l, int r, int idx){
// 	if (lazy[idx].ff == 0) return;
// 	if (lazy[idx].ff == 1){
// 		t[idx][0] = max(t[idx][0], lazy[idx].ss);
// 		t[idx][1] = max(t[idx][1], lazy[idx].ss);
// 	}else{
// 		t[idx][1] = min(t[idx][1], lazy[idx].ss);
// 		t[idx][0] = min(t[idx][0], lazy[idx].ss); 
// 	}
// 	if (l != r){
// 		lazy[idx<<1] = lazy[idx];
// 		lazy[idx<<1|1] = lazy[idx];
// 	}
// 	lazy[idx].ff = 0;
// }

void upd(int ind, int tp, int u, int v, int h, int l = 1, int r = NP, int idx = 1){
	// F(l, r, idx);
	if (l > v or r < u) return;
	if (u <= l and r <= v){
		if (tp == 1){
			t[idx][0] = max(t[idx][0], h);
			t[idx][1] = max(t[idx][1], h);
		}else{
			t[idx][1] = min(t[idx][1], h);
			t[idx][0] = min(t[idx][0], h); 
		}
		// if (l != r){
		// 	if (t[idx<<1][1] < t[idx][0]) t[idx<<1][0] = t[idx<<1][1] = t[idx][0];
		// 	else if (t[idx<<1][0] > t[idx][1]) t[idx<<1][0] = t[idx<<1][1] = t[idx][1];
		// 	else{
		// 		t[idx<<1][0] = max(t[idx<<1][0], t[idx][0]);
		// 		t[idx<<1][1] = min(t[idx<<1][1], t[idx][1]);
		// 	}
		// 	if (t[idx<<1|1][1] < t[idx][0]) t[idx<<1|1][0] = t[idx<<1|1][1] = t[idx][0];
		// 	else if (t[idx<<1|1][0] > t[idx][1]) t[idx<<1|1][0] = t[idx<<1|1][1] = t[idx][1];
		// 	else{
		// 		t[idx<<1|1][0] = max(t[idx<<1|1][0], t[idx][0]);
		// 		t[idx<<1|1][1] = min(t[idx<<1|1][1], t[idx][1]);
		// 	}
		// 	t[idx][0] = 0;
		// 	t[idx][1] = inf;
		// }
		pos[idx] = ind; 
		return;
	}
	int md = (l+r)>>1;
	upd(ind, tp, u, v, h, l, md, idx<<1);
	upd(ind, tp, u, v, h, md+1, r, idx<<1|1);
}

int tap(int index, int l = 1, int r = NP, int idx = 1){
	// F(l, r, idx);
	if (l == r) return min(t[idx][0], t[idx][1]);
	int md = (l+r)>>1;
	t[idx<<1][0] = max(t[idx<<1][0], t[idx][0]);
	t[idx<<1][1] = min(t[idx<<1][1], t[idx][1]); 
	t[idx<<1|1][0] = max(t[idx<<1|1][0], t[idx][0]); 
	t[idx<<1|1][1] = min(t[idx<<1|1][1], t[idx][1]); 
	if (pos[idx<<1] < pos[idx]){
		t[idx<<1][1] = max(t[idx<<1][1], t[idx<<1][0]);
	}
	if (pos[idx<<1|1] < pos[idx]){
		t[idx<<1|1][1] = max(t[idx<<1|1][1], t[idx<<1|1][0]);
	}
	if (index <= md) return tap(index, l, md, idx<<1);
	return tap(index, md+1, r, idx<<1|1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	NP = n;
	for (int i = 1; i <= 4*n; i++) t[i][1] = inf;
	for (int i = 0; i < k; i++){
		upd(i, op[i], left[i]+1, right[i]+1, height[i]);
	}
	for (int i = 0; i < n; i++) finalHeight[i] = tap(i+1);
}

// int main ()
// {
// 	ios::sync_with_stdio(false);
// 	cin.tie(0);
// 	int n, q; 
// 	cin >> n >> q;
// 	for (int i = 1; i <= 4*n; i++) t[i][1] = inf;
// 	while(q--){
// 		int tp, l, r, h;
// 		cin >> tp >> l >> r >> h;
// 		upd(tp, l+1, r+1, h);
// 	}
// 	for (int i = 1; i <= n; i++) cout << tap(i) << " ";
// }

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 119 ms 8036 KB Output is correct
3 Incorrect 103 ms 4460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -