제출 #1030888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1030888		tolbi	벽 (IOI14_wall)	C++17	24 / 100	344 ms	22720 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 1e9+7;
#define tol(bi) (1LL<<((int)(bi)))
void _upd(array<int,4> &old, array<int,3> upd){
	if (upd[1]==1){
		if (old[0]<=upd[0]){
			old[0]=min(old[2],max(old[0],upd[0]));
			old[1]=upd[2];
		}
	}
	else {
		if (old[2]>=upd[0]){
			old[2]=max(old[0],min(old[2],upd[0]));
			old[3]=upd[2];
		}
	}
}
struct SegTree{
	vector<array<int,4>> segtree;
	SegTree(int n){
		segtree.resize(tol(ceil(log2(n)+1))-1,{0,MOD,MOD,MOD});
	}
	void update(int tl, int tr, array<int,3> val, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		if (l>=tl && r<=tr){
			_upd(segtree[node],val);
			return;
		}
		if (l>tr || r<tl) return;
		int mid = l+(r-l)/2;
		if (tl<=mid) update(tl, tr, val, l, mid, node*2+1);
		if (mid<tr) update(tl, tr, val, mid+1, r, node*2+2);
	}
	int query(int x){
		int l = 0, r = segtree.size()/2;
		int node = 0;
		array<int,4> pr = {0,MOD,MOD,MOD};
		vector<array<int,3>> upds;
		upds.push_back({segtree[node][0],1,segtree[node][1]});
		upds.push_back({segtree[node][2],2,segtree[node][3]});
		while (l<r){
			int mid = l+(r-l)/2;
			if (x<=mid){
				r=mid;
				node=node*2+1;
			}
			else {
				l=mid+1;
				node=node*2+2;
			}
			upds.push_back({segtree[node][0],1,segtree[node][1]});
			upds.push_back({segtree[node][2],2,segtree[node][3]});
		}
		sort(upds.begin(), upds.end(), [&](array<int,3> &a, array<int,3> &b){
			return a[2]>b[2];
		});
		for (auto &it : upds){
			_upd(pr,it);
		}
		return pr[0];
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	SegTree segtree(n);
	for (int i = k-1; i >= 0; i--){
		segtree.update(left[i],right[i],{height[i],op[i],i});
	}
	for (int i = 0; i < n; ++i)
	{
		finalHeight[i]=segtree.query(i);
	}
}

• Subtask 1: 0 / 8
• Subtask 2: 24 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39