Submission #308348

#	Time	Username	Problem	Language	Result	Execution time	Memory
308348		super_j6	Wall (IOI14_wall)	C++14	0 / 100	173 ms	15224 KiB

wall

#include "wall.h"
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int inf = 0x3f3f3f3f;

struct segTree{
	int l, r;
	segTree *tl, *tr;
	int mx1, mx2, mxl, mn1, mn2, mnl;
	
	segTree(int a, int b){
		l = a, r = b;
		mx1 = mn1 = 0, mx2 = -inf, mn2 = inf, mxl = mnl = -1;
		if(l != r){
			int mid = (l + r) / 2;
			tl = new segTree(l, mid);
			tr = new segTree(mid + 1, r);
		}
	}
	
	void upx(int x){
		if(mx1 == mn1) mx1 = x;
		if(mx2 == mn1) mx2 = x;
		mn1 = x, mnl = x;
	}
	
	void upn(int x){
		if(mn1 == mx1) mn1 = x;
		if(mn2 == mx1) mn2 = x;
		mx1 = x, mnl = x;
	}
	
	void pull(){
		mx1 = max(tl->mx1, tr->mx1);
		mx2 = max(tl->mx2, tr->mx2);
		if(tl->mx1 != mx1) mx2 = max(mx2, tl->mx1);
		if(tr->mx1 != mx1) mx2 = max(mx2, tr->mx1);
		
		mn1 = min(tl->mn1, tl->mn1);
		mn2 = min(tl->mn2, tr->mn2);
		if(tl->mn1 != mn1) mn2 = min(mn2, tl->mn2);
		if(tr->mn1 != mn1) mn2 = min(mn2, tr->mn2);
	}
	
	void push(){
		if(~mxl) tl->upx(mxl), tr->upx(mxl);
		if(~mnl) tl->upn(mnl), tr->upn(mnl);
		mxl = mnl = -1;
	}
	
	void adx(int a, int b, int v){
		if(b < l || r < a || v <= mn1) return;
		if(a <= l && r <= b && v < mn2) return upx(v);
		tl->push(), tr->push();
		tl->adx(a, b, v), tr->adx(a, b, v);
		pull();
	}
	
	void adn(int a, int b, int v){
		if(b < l || r < a || v >= mx1) return;
		if(a <= l && r <= b && v > mx2) return upn(v);
		tl->push(), tr->push();
		tl->adx(a, b, v), tr->adx(a, b, v);
		pull();
	}
	
	void sol(int ans[]){
		if(l == r) return (void)(ans[l] = mn1);
		tl->push(), tr->push();
		tl->sol(ans), tr->sol(ans);
	}
};

void buildWall(int n, int k, int a[], int l[], int r[], int h[], int ans[]){
	segTree tre(0, n - 1);
	
	for(int i = 0; i < k; i++){
		if(a[i] & 1) tre.adx(l[i], r[i], h[i]);
		else tre.adn(l[i], r[i], h[i]);
	}
	
	tre.sol(ans);
}

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