Submission #49574

#	Time	Username	Problem	Language	Result	Execution time	Memory
49574		khsoo01	Wall (IOI14_wall)	C++11	100 / 100	1309 ms	162944 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int L = (1<<21), inf = 1e9;

struct SEG {
	int mn[2*L], mx[2*L];
	void init () {
		for(int i=2*L;i--;) {
			mn[i] = 0;
			mx[i] = inf;
		}
	}
	void relax (int P, int O, int V) {
		if(O == 1) {
			mn[P] = max(mn[P], V);
			if(mn[P] > mx[P]) mx[P] = mn[P];
		}
		else {
			mx[P] = min(mx[P], V);
			if(mn[P] > mx[P]) mn[P] = mx[P];
		}
	}
	void lazydown (int P) {
		relax(2*P, 1, mn[P]);
		relax(2*P, 2, mx[P]);
		relax(2*P+1, 1, mn[P]);
		relax(2*P+1, 2, mx[P]);
		mn[P] = 0;
		mx[P] = inf;
	}
	void upd (int S, int E, int O, int V, int SS = 0, int SE = L-1, int P = 1) {
		if(S <= SS && SE <= E) {
			relax(P, O, V);
			return;
		}
		if(E < SS || SE < S) return;
		lazydown(P);
		int M = (SS+SE)/2;
		upd(S, E, O, V, SS, M, 2*P);
		upd(S, E, O, V, M+1, SE, 2*P+1);
	}
	int get (int I, int SS = 0, int SE = L-1, int P = 1) {
		if(SS == SE) return mn[P];
		lazydown(P);
		int M = (SS+SE)/2;
		return I <= M ? get(I, SS, M, 2*P) : get(I, M+1, SE, 2*P+1);
	}
} seg;

void buildWall (int N, int K, int O[], int L[], int R[], int H[], int FH[]){
	seg.init();
	for(int i=0;i<K;i++) {
		seg.upd(L[i], R[i], O[i], H[i]);
	}
	for(int i=0;i<N;i++) {
		FH[i] = seg.get(i);
	}
}

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