Submission #329050

#	Time	Username	Problem	Language	Result	Execution time	Memory
329050		super_j6	Wall (IOI14_wall)	C++14	100 / 100	964 ms	224872 KiB

wall

#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 mn = 0, mx = inf;
	
	segTree(int a, int b){
		l = a, r = b;
		mn = 0, mx = inf;
		if(l != r){
			int mid = (l + r) / 2;
			tl = new segTree(l, mid);
			tr = new segTree(mid + 1, r);
		}
	}
	
	void upd(int vl, int vr){
		mn = min(max(mn, vl), vr);
		mx = min(max(mx, vl), vr);
	}
	
	void psh(){
		tl->upd(mn, mx), tr->upd(mn, mx);
		mn = 0, mx = inf;
	}
	
	void add(int a, int b, int vl, int vr){
		if(b < l || r < a) return;
		if(a <= l && r <= b) return upd(vl, vr);
		psh();
		tl->add(a, b, vl, vr), tr->add(a, b, vl, vr);
	}
	
	void sol(int ans[]){
		if(l == r) return (void)(ans[l] = mn);
		psh();
		tl->sol(ans), tr->sol(ans);
	}
};

void buildWall(int n, int q, int t[], int l[], int r[], int h[], int ans[]){
	segTree tre(0, n - 1);
	
	for(int i = 0; i < q; i++){
		if(t[i] & 1) tre.add(l[i], r[i], h[i], inf);
		else tre.add(l[i], r[i], 0, h[i]);
	}
	
	tre.sol(ans);
}

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