제출 #726815

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
726815		allin27x	벽 (IOI14_wall)	C++17	100 / 100	739 ms	99444 KiB

wall

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long int;
struct SGT{
	int t[(int)8e6][2] = {{0, (int)2e9}};
	int n;
	int ofs;
	SGT(int sz){
		n= sz;
		ofs = 1ll<<(int)(ceil(log2(n+1)));
	}

	void apply(int p){
		if (t[p][0]>t[2*p][1]) t[2*p][0]=t[p][0],t[2*p][1]=t[p][0]; else
		if (t[2*p][0]>t[p][1]) t[2*p][0]=t[p][1], t[2*p][1]=t[p][1]; else
		t[2*p][0]=max(t[2*p][0],t[p][0]), t[2*p][1]=min(t[2*p][1], t[p][1]);

		if (t[p][0]>t[2*p+1][1]) t[2*p+1][0]=t[p][0],t[2*p+1][1]=t[p][0]; else
		if (t[2*p+1][0]>t[p][1]) t[2*p+1][0]=t[p][1], t[2*p+1][1]=t[p][1]; else
		t[2*p+1][0]=max(t[2*p+1][0],t[p][0]), t[2*p+1][1]=min(t[2*p+1][1], t[p][1]);

		t[p][0] = 0; t[p][1] = (int)2e9;
	}

	void update(int p, int tl, int tr, int l ,int r, int h, int o){

		if (p<ofs) apply(p);
		if (l>r) return;
		if (tl==l && tr==r){
            if (o==0){
                t[p][0] = max(t[p][0], h); t[p][1] = max(t[p][1], t[p][0]);
            } else {
                t[p][1] = min(t[p][1], h); t[p][0] = min(t[p][0], t[p][1]);
            }
			return;
		}
		int tm = (tl+tr)>>1;
		update(2*p, tl, tm, l, min(tm, r), h, o);
		update(2*p+1, tm+1, tr, max(l,tm+1), r, h, o);
	}

	void update(int l, int r, int h, int o){

		update(1, 0, ofs-1, l, r, h, o);
	}

	void push(){
		for (int i=1; i<ofs; i++){
			apply(i);
		}
	}
};


void buildWall(int n, int k, int op[], int l[],int r[],int h[], int ans[]){
	SGT st(n);
	for (int i=0; i<k; i++){
		st.update(l[i], r[i], h[i], op[i]-1);
	}
	st.push();
	for (int i=0; i<n; i++) ans[i] = min(st.t[i+st.ofs][0], st.t[i+st.ofs][1]);
}

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