Submission #789431

#	Time	Username	Problem	Language	Result	Execution time	Memory
789431		OrazB	Wall (IOI14_wall)	C++14	0 / 100	3 ms	468 KiB

wall

#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;
int n, q, t[4*N][2];
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 tp, int u, int v, int h, int l = 1, int r = n, int idx = 1){
	F(l, r, idx);
	if (l > v or r < u) return;
	if (u <= l and r <= v){
		lazy[idx] = {tp, h};
		F(l, r, idx);
		return;
	}
	int md = (l+r)>>1;
	upd(tp, u, v, h, l, md, idx<<1);
	upd(tp, u, v, h, md+1, r, idx<<1|1);
	t[idx][0] = min(t[idx<<1][0], t[idx<<1|1][0]);
	t[idx][1] = max(t[idx<<1][1], t[idx<<1|1][1]);
}

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

// int main ()
// {
// 	ios::sync_with_stdio(false);
// 	cin.tie(0);
// 	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
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39