Submission #303554

#	Time	Username	Problem	Language	Result	Execution time	Memory
303554		colazcy	Plahte (COCI17_plahte)	C++17	0 / 160	769 ms	28984 KiB

plahte

#include <cstdio>
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 100;
vector<int> G[maxn];
inline void addedge(int u,int v){G[u].push_back(v);}
struct node{
	int l,r;
	mutable int v;
	inline bool operator < (const node &rhs)const{return l < rhs.l;}
};
typedef set<node>::iterator iter;
set<node> s;
inline iter split(int x){
	iter it = s.upper_bound(node{x,0,0});
	--it;
	if(it->l == x)return it;
	int l = it->l,r = it->r,v = it->v;
	s.erase(it);
	s.insert(node{l,x - 1,v});
	return s.insert(node{x,r,v}).first;
}
inline void assign(int l,int r,int v){
	iter itr = split(r + 1),itl = split(l);
	s.erase(itl,itr);
	s.insert(node{l,r,v});
}
inline int query(int pos){
	iter it = s.upper_bound(node{pos,0,0});
	--it;
	return it->v;
}
struct seg{
	int x,l,r,id,opt;
	bool operator < (const seg &rhs)const{
		if(x != rhs.x)return x < rhs.x;
		return opt > rhs.opt;
	}
}val[maxn << 1];
int n,m,tot,faz[maxn],col[maxn],ans[maxn];
inline void merge(set<int> &a,set<int> &&b){
	if(a.size() < b.size())swap(a,b);
	for(int x : b)a.insert(x);
}
set<int> dfs(int u){
	set<int> res;
	if(col[u])res.insert(u);
	for(int v : G[u])merge(res,dfs(v));
	ans[u] = res.size();
	return res;
}
int main(){
//#ifdef LOCAL
//	freopen("fafa.in","r",stdin);
//#else
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//#endif
	cin >> n >> m;
	for(int a,b,c,d,i = 1;i <= n;i++){
		cin >> a >> b >> c >> d;
		val[++tot] = seg{a,b,d,i,3};
		val[++tot] = seg{c,b,d,-i,1};
	}
	for(int x,y,i = 1;i <= m;i++){
		cin >> x >> y >> col[n + i];
		val[++tot] = seg{x,y,y,n + i,2};
	}
	sort(val + 1,val + 1 + tot);
	s.insert(node{(int)-2e9,(int)2e9});
	for(int i = 1;i <= tot;i++)
		if(val[i].id > 0){
			faz[val[i].id] = query(val[i].l);
			assign(val[i].l,val[i].r,val[i].id);
		}else assign(val[i].l,val[i].r,faz[-val[i].id]);
	for(int i = 1;i <= n + m;i++)
		addedge(faz[i],i);
	dfs(0);
	for(int i = 1;i <= n;i++)
		cout << ans[i] << '\n';
	return 0;
}

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