Submission #1088362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088362		Sunbae	Wall (IOI14_wall)	C++17	0 / 100	78 ms	188244 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);  
	}
	fH = A;
	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);
		}
	}
}	
/*
signed main(){
	int n, k; scanf("%d %d", &n, &k);
	int op[k], l[k], r[k], H[k];
	for(int i = 0; i<k; ++i){
		scanf("%d %d %d %d", op+i, l+i, r+i, H+i);
	}
	int* fH;
	buildWall(n, k, op, l, r, H, fH);
	for(int i = 0; i<n; ++i) printf("%d ", A[i]);
}
*/	

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