oj.uz

Submission #306403

# Submission time Handle Problem Language Result Execution time Memory
306403 2020-09-25T12:33:21 Z colazcy Plahte (COCI17_plahte) C++17
160 / 160
 402 ms 35520 KB 
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <set>
#include <vector>
#include <cstring>
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(son[u] == -1 || 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){
//	printf("%d %d\n",u,son[u]);
	for(int v : G[u]){
		if(v == son[u])continue;
		dfs(v,0);
	}
	if(son[u] != -1)dfs(son[u],1),vis[son[u]] = 1;
	calc(u,1);
	if(son[u] != -1)vis[son[u]] = 0;
	ans[u] = now;
	if(!keep)calc(u,-1);
}
int main(){
//	freopen("plahte.in.1a","r",stdin);
//	freopen("plahte.out","w",stdout);
	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);
	memset(son,-1,sizeof(son));
	predfs(0);
	dfs(0,0);
	for(int i = 1;i <= n;i++)printf("%d\n",ans[i]); 
	return 0;
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 18424 KB Output is correct
2 Correct 117 ms 17912 KB Output is correct
3 Correct 9 ms 14080 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 22136 KB Output is correct
2 Correct 134 ms 19832 KB Output is correct
3 Correct 9 ms 14208 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 27768 KB Output is correct
2 Correct 226 ms 22008 KB Output is correct
3 Correct 9 ms 14080 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 35520 KB Output is correct
2 Correct 402 ms 25848 KB Output is correct
3 Correct 10 ms 14080 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 33656 KB Output is correct
2 Correct 371 ms 25460 KB Output is correct
3 Correct 11 ms 14080 KB Output is correct