제출 #1270751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270751		cheater_triet	Plahte (COCI17_plahte)	C++17	0 / 160	214 ms	51788 KiB

plahte

#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define st first
#define se second
typedef long long ll;
typedef long double lb;
typedef pair<ll, ll> ii;

const int INF = 1e9 + 4;
const ll LINF = 1e18;
const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0 ,0};
const int N = (int)2e5 + 4;

bool tmp(array<int, 3> x, array<int, 3> y) {
	if(x[0] == y[0]) {
		if(x[2] == y[2]) {
			if(x[2]) return x[1] > y[1];
			else return x[1] < y[1];  
		}
		return x[2] < y[2];
	}
	return x[0] < y[0]; 
}

int n, m;
int a[N], b[N], c[N], d[N], colour[N];
int par[N];
vector<int> g[N]; 
set<int> ans[N], st, t; 

void dfs(int u) {
	if(u > n) {
		assert(g[u].size() == 0);
		ans[u].insert(colour[u]); 
		return;
	}
	st.clear(); 
	for(int v : g[u]) {
		assert(v != par[u]); 
		dfs(v); 
		
		t = ans[v];
		if(t.size() > st.size()) swap(st, t); 
		for(auto it : t) st.insert(it); 
	}
	ans[u] = st; 
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

//	freopen("test.inp","r",stdin);
//	freopen("test.out","w",stdout);

	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i]; 
	}
	for(int i = n + 1; i <= n + m; i++) {
		int x, y; cin >> x >> y >> colour[i]; 
		a[i] = c[i] = x;
		b[i] = d[i] = y;
	}
	
	vector<array<int, 3>> val;
	for(int i = 1; i <= n + m; i++) {
		val.push_back({a[i], i, 0}); 
		val.push_back({c[i], i, 1});
	}
	
	sort(all(val), tmp);
	
	set<ii> s = {{INF,0}}; 
	for(auto arr : val) {
		int x = arr[0], id = arr[1], ok = arr[2]; 
		if(!ok) {
			auto it = s.lower_bound({b[id], -INF});
			ii v = *it; 
			
			if(v.se < 0) par[id] = -v.se;
			else par[id] = par[v.se];
			
			if(id > n) continue;
			s.insert({b[id], id}); 
			s.insert({d[id], -id});
		}
		else {
			if(id > n) continue;
			s.erase(s.find({b[id], id}));
			s.erase(s.find({d[id], -id}));
		}
	}
	
	for(int i = 1; i <= n + m; i++) {
		g[par[i]].push_back(i); 
	}
	
	dfs(0); 
	
	for(int i = 1; i <= n; i++) cout << ans[i].size() << '\n'; 
}

• Subtask 1: 0 / 32
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32
• Subtask 5: 0 / 32