oj.uz

Submission #306252

# Submission time Handle Problem Language Result Execution time Memory
306252 2020-09-25T03:34:02 Z colazcy Plahte (COCI17_plahte) C++17
160 / 160
 411 ms 42748 KB 
#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,col[maxn],ans[maxn],faz[maxn];
inline void merge(set<int> &a,set<int> &b){
	if(a.size() < b.size())swap(a,b);
	for(set<int>::iterator it = b.begin();it != b.end();it++)a.insert(*it);
}
inline set<int> dfs(int u){
	set<int> res;
	if(col[u])res.insert(col[u]);
	set<int> tmp;
	for(unsigned int i = 0;i < G[u].size();i++){
		int v = G[u][i];
		tmp = dfs(v);
		merge(res,tmp);
	}
	ans[u] = res.size();
	return res;
}
int main(){
//	freopen("plahte.in","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);
	dfs(0);
	for(int i = 1;i <= n;i++)printf("%d\n",ans[i]);
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 17528 KB Output is correct
2 Correct 122 ms 17528 KB Output is correct
3 Correct 9 ms 12032 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 22648 KB Output is correct
2 Correct 136 ms 19320 KB Output is correct
3 Correct 9 ms 12032 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 31244 KB Output is correct
2 Correct 227 ms 22776 KB Output is correct
3 Correct 9 ms 12032 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 42748 KB Output is correct
2 Correct 390 ms 28148 KB Output is correct
3 Correct 9 ms 12032 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 38976 KB Output is correct
2 Correct 374 ms 28460 KB Output is correct
3 Correct 9 ms 12160 KB Output is correct