제출 #1127221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127221		Math4Life2020	Wall (IOI14_wall)	C++20	32 / 100	3095 ms	11504 KiB

wall

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,sse4,bmi,bmi2,fma")
using ll = int; using pii = pair<ll,ll>;

const ll Nm = 131072; const ll E = 17;
vector<pii> st; //{min,max}

ll v2(ll x) {
	return (__builtin_ctz(x));
}

ll l2(ll x) {
	return (31-__builtin_clz(x));
}

pii fz(pii p1, pii p2) {
	return {min(p1.first,p2.first),max(p1.second,p2.second)};
}

void chmin(ll p, ll nf, ll ht0) {
	//cout << "chmin at p,nf="<<p<<","<<nf<<"\n";
	if (st[p].first>=nf) {
		//cout << "breaking\n";
		return;
	}
	if (p>=Nm) {
		//cout << "setting\n";
		st[p]={nf,nf};
	} else {
		chmin(2*p,nf,ht0);
		chmin(2*p+1,nf,ht0);
		st[p]=fz(st[2*p],st[2*p+1]);
	}
	ll ht = l2(p);
	assert(ht>=ht0);
	if (ht!=ht0) {
		return;
	}
	p=p/2;
	while (p>0) {
		st[p]=fz(st[2*p],st[2*p+1]);
		p=p/2;
	}
}

void chminI(ll l, ll r, ll nf) {
	if (l>r) {
		return;
	}
	ll vl = v2(l); ll vr = v2(r+1);
	if (vl<vr) {
		chmin((l>>vl)+(1<<(E-vl)),nf,E-vl);
		chminI(l+(1<<vl),r,nf);
	} else {
		chmin((r>>vr)+(1<<(E-vr)),nf,E-vr);
		chminI(l,r-(1<<vr),nf);
	}
}


void chmax(ll p, ll nf, ll ht0) {
	//cout << "chmax at p="<<p<<", nf="<<nf<<"\n";
	if (st[p].second<=nf) {
		//cout << "breaking\n";
		return;
	}
	if (p>=Nm) {
		//cout << "setting\n";
		st[p]={nf,nf};
	} else {
		chmax(2*p,nf,ht0);
		chmax(2*p+1,nf,ht0);
		st[p]=fz(st[2*p],st[2*p+1]);
	}
	ll ht = l2(p);
	assert(ht>=ht0);
	if (ht!=ht0) {
		return;
	}
	p=p/2;
	while (p>0) {
		st[p]=fz(st[2*p],st[2*p+1]);
		p=p/2;
	}
}

void chmaxI(ll l, ll r, ll nf) {
	//cout << "chmaxI: "<<l<<","<<r<<","<<nf<<"\n";
	if (l>r) {
		return;
	}
	ll vl = v2(l); ll vr = v2(r+1);
	if (vl<vr) {
		chmax((l>>vl)+(1<<(E-vl)),nf,E-vl);
		chmaxI(l+(1<<vl),r,nf);
	} else {
		chmax((r>>vr)+(1<<(E-vr)),nf,E-vr);
		chmaxI(l,r-(1<<vr),nf);
	}
}

void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
	st.clear();
	for (ll i=0;i<(2*Nm);i++) {
		st.push_back({0,0});
	}
	for (ll k=0;k<K;k++) {
		if (op[k]==1) {
			chminI(left[k],right[k],height[k]);
		} else {
			chmaxI(left[k],right[k],height[k]);
		}
	}
	for (ll i=0;i<N;i++) {
		finalHeight[i]=st[Nm+i].first;
	}
}

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