Submission #1127224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127224		Math4Life2020	Wall (IOI14_wall)	C++20	32 / 100	3094 ms	11488 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 pdn(ll p) {
	if (p>=Nm) {
		return;
	}
	st[p]=fz(st[2*p],st[2*p+1]);
}

void chmin(ll p, ll nf) {
	//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);
		chmin(2*p+1,nf);
		st[p]=fz(st[2*p],st[2*p+1]);
	}
}

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);
		chminI(l+(1<<vl),r,nf);
	} else {
		chmin((r>>vr)+(1<<(E-vr)),nf);
		chminI(l,r-(1<<vr),nf);
	}
}


void chmax(ll p, ll nf) {
	//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);
		chmax(2*p+1,nf);
		st[p]=fz(st[2*p],st[2*p+1]);
	}
}

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);
		chmaxI(l+(1<<vl),r,nf);
	} else {
		chmax((r>>vr)+(1<<(E-vr)),nf);
		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 e=1;e<=E;e++) {
			pdn((left[k]>>e)+(1<<(E-e)));
			pdn((right[k]>>e)+(1<<(E-e)));
		}
	}
	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