제출 #492633

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
492633		8e7	Wall (IOI14_wall)	C++17	100 / 100	917 ms	84420 KiB

wall

//Challenge: Accepted
#include "wall.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <assert.h>
#include <cmath>
#include <iomanip>
#include <random>
#include <unordered_set>
using namespace std;
void debug(){cout << endl;};
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b ...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
};
#define ll long long
#define maxn 2000005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 8e7;
struct segtree{
	int mi[4*maxn], ma[4*maxn], fi[4*maxn], a[maxn];	
	void init(int cur, int l, int r) {
		if (r <= l) return;
		mi[cur] = inf, ma[cur] = 0;
		if (r - l == 1) return;
		int m = (l + r) / 2;
		init(cur*2, l, m), init(cur*2+1, m, r);
	}
	void add(int ind, int type, int val) {
		if (type == 0 && val < mi[ind]) mi[ind] = val, fi[ind] = 1;
		if (type == 1 && val > ma[ind]) ma[ind] = val, fi[ind] = 0;
		if (fi[ind]) ma[ind] = min(ma[ind], mi[ind]);
		else mi[ind] = max(mi[ind], ma[ind]);
	}
	void push(int cur, int l, int r) {
		if (r - l > 1) {
			if (!fi[cur]) {
				add(cur*2, 0, mi[cur]), add(cur*2, 1, ma[cur]);
				add(cur*2+1, 0, mi[cur]), add(cur*2+1, 1, ma[cur]);
			} else {
				add(cur*2, 1, ma[cur]), add(cur*2, 0, mi[cur]);
				add(cur*2+1, 1, ma[cur]), add(cur*2+1, 0, mi[cur]);
			}
		} else {
			if (fi[cur]) a[l] = min(max(a[l], ma[cur]), mi[cur]);
			else a[l] = max(min(a[l], mi[cur]), ma[cur]);
		}
		ma[cur] = 0, mi[cur] = inf, fi[cur] = 0;
	}
	void modify(int cur, int l, int r, int ql, int qr, int val, int type) {
		if (r <= l || qr <= l || ql >= r) return;
		push(cur, l, r);
		if (ql <= l && qr >= r) {
			if (type) ma[cur] = val;
			else mi[cur] = val;		
			return;
		}
		int m = (l + r) / 2;
		modify(cur*2, l, m, ql, qr, val, type);
		modify(cur*2+1, m, r, ql, qr, val, type);
	}
	void build(int cur, int l, int r) {
		if (r <= l) return;
		push(cur, l, r);
		if (r - l == 1) return;
		int m = (l + r) / 2;
		build(cur*2, l, m), build(cur*2+1, m, r);	
	}
} seg;
void buildWall(int n, int k, int op[], int lef[], int rig[], int h[], int ret[]) {
	seg.init(1, 0, n);
	for (int i = 0;i < k;i++) {
		seg.modify(1, 0, n, lef[i], rig[i]+1, h[i], 2 - op[i]);	
	}
	seg.build(1, 0, n);
	for (int i = 0;i < n;i++) ret[i] = seg.a[i];
}
/*
5 5
1 0 4 5
2 2 3 2
1 1 2 4
2 2 4 1
1 1 3 3

4 6
1 3 3 1
1 1 2 2
1 0 0 4
2 0 1 2
*/

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