제출 #1088363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1088363		Sunbae	Wall (IOI14_wall)	C++17	8 / 100	3088 ms	235960 KiB

wall

#include <bits/stdc++.h>
#define z exit(0)
using namespace std;
const int N = 2e6 + 1;
vector<tuple<int,int,int>> s[N<<2];
int L, R, v, ti, o, idx[N], A[N];
tuple<int,int,int> T[N];
void ini(int I, int lo, int hi){
	if(lo == hi){ idx[lo] = I; return;}
	int m = lo + ((hi-lo)>>1);
	ini(I<<1, lo, m); ini(I<<1|1, m+1, hi);
}
void upd(int I, int lo, int hi){
	if(lo > R || hi < L) return;
	if(L <= lo && hi <= R){ s[I].emplace_back(ti, o, v); return;}
	int m = lo + ((hi-lo)>>1);
	upd(I<<1, lo, m); upd(I<<1|1, m+1, hi);
}

void buildWall(int n, int k, int op[], int l[], int r[], int H[], int fH[]){
	for(int i = 0; i<(n<<2); ++i) s[i].clear();
	ini(1, 0, n-1);
	for(ti = 0; ti<k; ++ti){
		L = l[ti]; R = r[ti]; o = op[ti]-1; v = H[ti]; 
		upd(1, 0, n-1);  
	}
	for(int i = 0; i<n; ++i){
		int m = 0;
		for(int I = idx[i]; I; I>>=1) for(auto it : s[I]) T[m++] = it;
		sort(T, T+m);
		fH[i] = 0;
		for(int j = 0; j<m; ++j){
			auto it = T[j];
			o = get<1>(it); v = get<2>(it);
			fH[i] = !o ? max(fH[i], v) : min(fH[i], v);
		}
	}
}	

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