제출 #774331

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
774331		phoenix0423	벽 (IOI14_wall)	C++17	100 / 100	1058 ms	224588 KiB

wall

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
typedef tuple<ll, ll, ll> tll;
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define v vector
#define ckmax(a, b) a = max(a, b)
#define ckmin(a, b) a = min(a, b)
#define fastio ios::sync_with_stdio(false), cin.tie(0)
const int N = 1e9 + 7;
const int maxn = 2e6 + 5;
#pragma GCC optimize("Ofast")
int n;
struct Tag{
	ll l, r, alive;
	Tag(){alive = 0;}
	Tag(ll _l, ll _r) : l(_l), r(_r), alive(1){}
};
struct node{
	Tag tag;
	node(){}
};
node st[maxn * 4];
Tag cast(Tag a, Tag b){
	if(a.alive + b.alive < 2) return (a.alive ? a : b);
	if(a.l < b.l) a.l = b.l;
	else if(a.l > b.r) a.l = b.r;
	if(a.r > b.r) a.r = b.r;
	else if(a.r < b.l) a.r = b.l;
	return a;
}
void push(int v){
	st[v * 2].tag = cast(st[v * 2].tag, st[v].tag);
	st[v * 2 + 1].tag = cast(st[v * 2 + 1].tag, st[v].tag);
	st[v].tag = Tag();
}
void upd(int op, int l, int r, ll h, int v = 1, int L = 0, int R = n - 1){
	if(l > R || r < L) return;
	if(l <= L && r >= R){
		if(op == 1) st[v].tag = cast(st[v].tag, Tag(h, 1e18));
		else st[v].tag = cast(st[v].tag, Tag(0, h));
		return;
	}			
	push(v);
	int m = (L + R) / 2;
	upd(op, l, r, h, v * 2, L, m);
	upd(op, l, r, h, v * 2 + 1, m + 1, R);
}

ll qry(int pos, int v = 1, int l = 0, int r = n - 1){
	if(l == r) return st[v].tag.l;
	push(v);
	int m = (l + r) / 2;
	if(pos <= m) return qry(pos, v * 2, l, m);
	else return qry(pos, v * 2 + 1, m + 1, r);
}
void buildWall(int siz, int k, int op[], int l[], int r[], int h[], int ret[]){
	n = siz;
	for(int i = 0; i < k; i++){
		upd(op[i], l[i], r[i], h[i]);
	}
	for(int i = 0; i < n; i++){
		ret[i] = qry(i);
	}
}
/*
void solve(){
	int n, k;
	cin>>n>>k;
	vector<int> op(k), left(k), right(k), height(k), finalheight(n);
	for(int i = 0; i < k; i++){
		cin>>op[i]>>left[i]>>right[i]>>height[i];
	}
	buildWall(n, k, op, left, right, height, finalheight);
	for(int i = 0; i < n; i++) cout<<finalheight[i]<<" ";
	cout<<"\n";
}

int main(void){
	fastio;
	// freopen("balancing.in", "r", stdin);
	// freopen("balancing.out", "w", stdout);
	int t = 1;
	// cin>>t;
	while(t--){
		solve();
	}
}*/
/*
10 6 
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/

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