Submission #1180183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180183		Alihan_8	Wall (IOI14_wall)	C++20	0 / 100	77 ms	8008 KiB

wall

#include "wall.h"

#include <bits/stdc++.h>

using namespace std;

void chmax(int &x, const int &y){ x = max(x, y); }
void chmin(int &x, const int &y){ x = min(x, y); }

const int inf = 1e8;

struct SegTree{
	struct Info{
		int mn1, mn2, mx1, mx2;
		
		Info() : mn1(0), mn2(inf), mx1(0), mx2(-inf) {}
		
		void merge(Info lf, Info rg){
			mx2 = -inf, mn2 = inf;
			
			mn1 = min(lf.mn1, rg.mn1);
			mx1 = max(lf.mx1, rg.mx1);
			
			for ( auto x: {lf.mx1, lf.mx2, rg.mx1, rg.mx2} ){
				if ( x != mx1 ) chmax(mx2, x);
			}
			
			for ( auto x: {lf.mn1, lf.mn2, rg.mn1, rg.mn2} ){
				if ( x != mn1 ) chmin(mn2, x);
			}
		}
	};
	
	vector <Info> seg;
	vector <int> lmx, lmn;
	
	int n;
	
	SegTree(int n) : seg(n * 4 + 5), lmx(n * 4 + 5, -inf), lmn(n * 4 + 5, inf), n(n) {}
	
	void push(int v, int l, int r){
		if ( l != r ){
			for ( auto x: {v * 2, v * 2 + 1} ){
				chmin(lmn[x], lmn[v]);
				chmax(lmx[x], lmx[v]);
			}
		}
		
		if ( seg[v].mx1 == seg[v].mn1 ){
			if ( lmn[v] < seg[v].mx1 ){
				seg[v].mx1 = seg[v].mn1 = lmn[v];
			} else{
				seg[v].mx1 = seg[v].mn1 = max(seg[v].mn1, lmx[v]);
			}
		} else{	
			if ( seg[v].mn1 == seg[v].mx2 ){
				seg[v].mn1 = seg[v].mx2 = max(seg[v].mn1, lmx[v]);
			} else chmax(seg[v].mn1, lmx[v]);
			
			if ( seg[v].mx1 == seg[v].mn2 ){
				seg[v].mx1 = seg[v].mn2 = min(seg[v].mx1, lmn[v]);
			} else chmin(seg[v].mx1, lmn[v]);
		}
		
		lmn[v] = inf, lmx[v] = -inf;
	}
	
	void upd_mx(int v, int l, int r, int tl, int tr, int x){
		push(v, l, r);
		
		if ( l > tr || r < tl || seg[v].mn1 >= x ) return;
		
		if ( tl <= l && tr >= r && seg[v].mn2 > x ){
			lmx[v] = x;
			
			if ( l != r ){
				int m = (l + r) / 2;
				
				push(v * 2, l, m);
				push(v * 2 + 1, m + 1, r);
			}
			
			push(v, l, r);
			
			return;
		}
		
		int m = (l + r) / 2;
		
		upd_mx(v * 2, l, m, tl, tr, x);
		upd_mx(v * 2 + 1, m + 1, r, tl, tr, x);	
		
		seg[v].merge(seg[v * 2], seg[v * 2 + 1]);
	}
	
	void ckmax(int l, int r, int x){
		upd_mx(1, 0, n - 1, l, r, x);
	}
	
	void upd_mn(int v, int l, int r, int tl, int tr, int x){
		push(v, l, r);
		
		if ( l > tr || r < tl || seg[v].mx1 <= x ) return;
		
		if ( tl <= l && tr >= r && seg[v].mx2 < x ){
			lmn[v] = x;
			
			if ( l != r ){
				int m = (l + r) / 2;
				
				push(v * 2, l, m);
				push(v * 2 + 1, m + 1, r);
			}
			
			push(v, l, r);
			
			return;
		}
		
		int m = (l + r) / 2;
		
		upd_mn(v * 2, l, m, tl, tr, x);
		upd_mn(v * 2 + 1, m + 1, r, tl, tr, x);
		
		seg[v].merge(seg[v * 2], seg[v * 2 + 1]);
	}
	
	void ckmin(int l, int r, int x){
		upd_mn(1, 0, n - 1, l, r, x);
	}
	
	int get(int v, int l, int r, int x){
		push(v, l, r);
		
		if ( l == r ) return seg[v].mx1;
		
		int m = (l + r) / 2;
		
		if ( x <= m ) return get(v * 2, l, m, x);
		
		return get(v * 2 + 1, m + 1, r, x);
	}
	
	int qry(int x){ return get(1, 0, n - 1, x); }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	SegTree seg(n);
	
	for ( int i = 0; i < k; i++ ){
		if ( op[i] == 1 ) seg.ckmax(left[i], right[i], height[i]);
		else seg.ckmin(left[i], right[i], height[i]);
		
		//~ for ( int i = 0; i < n; i++ ) cout << seg.qry(i) << ' ';
		//~ cout << '\n';
	}
	
	for ( int i = 0; i < n; i++ ){
		finalHeight[i] = seg.qry(i);
	}
}

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