Submission #306402

#	Time	Username	Problem	Language	Result	Execution time	Memory
306402		colazcy	Plahte (COCI17_plahte)	C++17	0 / 160	388 ms	33100 KiB

plahte

#include <cstdio>
#include <algorithm>
#include <cctype>
#include <set>
#include <vector>
using namespace std;
const int maxn = 5e5;
inline int read(){
	int x = 0;char c = getchar();
	while(!isdigit(c))c = getchar();
	while(isdigit(c))x = x * 10 + c - '0',c = getchar();
	return x;
}
vector<int> G[maxn];
inline void addedge(int u,int v){G[u].push_back(v);}
struct node{
	int l,r;
	mutable int v;
	node(int a,int b,int c):l(a),r(b),v(c){}
	bool operator < (const node &rhs)const{
		return l < rhs.l;
	}
};
set<node> s;
typedef set<node>::iterator iter;
inline iter split(int l){
	iter it = --s.upper_bound(node(l,0,0));
	if(it->l == l)return it;
	int L = it->l,R = it->r,V = it->v;
	s.insert(node(L,l - 1,V));
	return s.insert(node(l,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));
	return it->v;
}
struct Seg{
	int x,l,r,opt,id;
	bool operator < (const Seg &rhs)const{
		if(x != rhs.x)return x < rhs.x;
		return opt > rhs.opt;
	}
}seg[maxn];
int n,m,tot,now,cnt[maxn],col[maxn],ans[maxn],faz[maxn],siz[maxn],son[maxn],vis[maxn];
inline void add(int x){
	if(!cnt[x]++)now++;
}
inline void del(int x){
	if(!--cnt[x])now--;
}
inline void predfs(int u){
	siz[u] = 1;
	for(int v : G[u]){
		predfs(v);
		siz[u] += siz[v];
		if(siz[v] > siz[son[u]])son[u] = v;
	}
}
inline void calc(int u,int opt){
	if(col[u]){
		if(opt == 1)add(col[u]);
		else del(col[u]);
	}
	for(int v : G[u]){
		if(vis[v])continue;
		calc(v,opt);
	}
}
inline void dfs(int u,int keep){
	for(int v : G[u]){
		if(v == son[u])continue;
		dfs(v,0);
	}
	if(son[u])dfs(son[u],1),vis[son[u]] = 1;
	calc(u,1);vis[son[u]] = 0;
	ans[u] = now;
	if(!keep)calc(u,-1);
}
int main(){
	n = read(),m = read();
	for(int a,b,c,d,i = 1;i <= n;i++){
		a = read(),b = read(),c = read(),d = read();
		seg[++tot] = Seg{a,b,d,3,i};
		seg[++tot] = Seg{c,b,d,1,-i};
	}
	for(int x,y,i = 1;i <= m;i++){
		x = read(),y = read(),col[n + i] = read();
		seg[++tot] = Seg{x,y,y,2,n + i};
	}
	s.insert(node(-1e9,1e9,0));
	sort(seg + 1,seg + 1 + tot);
	for(int i = 1;i <= tot;i++){
		if(seg[i].id > 0){
			faz[seg[i].id] = query(seg[i].l);
			assign(seg[i].l,seg[i].r,seg[i].id);
		}else assign(seg[i].l,seg[i].r,faz[-seg[i].id]);
	}
	for(int i = 1;i <= tot;i++)addedge(faz[i],i);
	predfs(1);
	dfs(1,1);
	for(int i = 1;i <= n;i++)printf("%d\n",ans[i]); 
	return 0;
}

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