제출 #986565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
986565		vqpahmad	벽 (IOI14_wall)	C++14	100 / 100	584 ms	69640 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e6 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int off = (1<<21);
struct sgt {
#define ls (idx<<1)
#define rs (idx<<1|1)
	pii t[off * 2];
	pii unit = {0, inf};
	void init(){
		for (int i = 0; i < off * 2; i++){
			t[i] = unit;
		}
	}
	pii merge(pii lhs, pii rhs){
		// lhs.S     rhs.S
		// lhs.F     rhs.F
		if (lhs.F > rhs.S){
			return {rhs.S, rhs.S};
		}
		if (rhs.F > lhs.S){
			return {rhs.F, rhs.F};
		}
		return {max(lhs.F, rhs.F), min(lhs.S, rhs.S)};
	}
	void push(int idx){
		if (t[idx] == unit || idx >= off) return;
		t[ls] = merge(t[ls], t[idx]);
		t[rs] = merge(t[rs], t[idx]);
		t[idx] = unit;
	}
	void update(int l, int r, int op, int val, int idx=1, int lo=0, int hi=off){
		push(idx);
		if (r <= lo || hi <= l) 
			return;
		if (l <= lo && hi <= r){
			if (op == 1){
				t[idx] = merge(t[idx], {val, inf});
			} else if (op == 2){
				t[idx] = merge(t[idx], {0, val});
			}
			return;
		}
		int mi = (lo+hi)>>1;
		update(l, r, op, val, ls, lo, mi);
		update(l, r, op, val, rs, mi, hi);
		return;
	}
	void updateAll(){
		for (int i = 0; i < off; i++){
			push(i);
		}
	}
	void printO(){
		int pw = 1;
		int cnt = 0;
		for (int i = 1; i < off * 2; i++){
			cnt++;
			cout << "("<< (t[i].F == inf ? -1 : t[i].F) << ", " << (t[i].S == inf ? -1 : t[i].S) << ") ";
			if (cnt == pw){
				pw *= 2;
				cnt = 0 ;
				cout << endl;
			}
		}
	}
	void print(int n){
		
		updateAll();
		for (int i = 0; i < n; i++){
			cout << "("<< (t[i + off].F == inf ? -1 : t[i + off].F) << ", " << (t[i + off].S == inf ? -1 : t[i + off].S) << ") ";
		}
		cout << endl;
	}
} seg;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	seg.init();
	//seg.printO();
	for (int i = 0; i < k; i++){
		seg.update(left[i], right[i] + 1, op[i], height[i]);
		//seg.printO();
		//seg.print(n);
	}
	seg.updateAll();
	for (int i = 0; i < n; i++){
		finalHeight[i] = seg.t[i + off].F;
	}
}

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