제출 #172851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
172851		maximath_1	벽 (IOI14_wall)	C++11	0 / 100	171 ms	9720 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=1e18;
vector<ll> stmax, stmin, ans;
void down(ll idx, ll mn, ll mx){
	stmin[idx]=min(stmin[idx], mn);
	stmax[idx]=min(stmax[idx], mn);
	stmax[idx]=max(stmax[idx], mx);
} 
void upd(ll cl, ll cr, ll lf, ll rg, ll nd, ll valmn, ll valmx){
	if(cl==cr) ans[cl]=stmax[nd];
	else if(stmin[nd]!=inf || stmax[nd]!=0){
		down(nd*2, stmin[nd], stmax[nd]);
		down(nd*2+1, stmin[nd], stmax[nd]);
		stmin[nd]=inf;
		stmax[nd]=0;
	}
	if(cr<lf || rg<cl) return;
	else if(lf<=cl && cr<=rg)
		down(nd, valmn, valmx);
	else{
		upd(cl, (cl+cr)/2, lf, rg, nd*2, valmn, valmx);
		upd((cl+cr)/2, cr, lf, rg, nd*2+1, valmn, valmx);
	}
}
void buildWall(int n, int k, int op[], int lf[], int rg[], int H[], int fh[]){
	stmax.resize(4*n+1); stmin.resize(4*n+1); ans.resize(n+1);
	for(int i=1; i<=4*n; i++) {stmin[i]=inf; stmax[i]=0;}
	for(int i=0; i<k; i++){
		if(op[i]==1)
			upd(0, n-1, lf[i], rg[i], 1, inf, H[i]);
		else
			upd(0, n-1, lf[i], rg[i], 1, H[i], 0);
	}
	for(int i=0; i<n; i++)
		upd(0, n-1, i, i, 1, inf, 0);
	for(int i=0; i<n; i++)
		fh[i]=ans[i];
}

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