Submission #330722

#	Time	Username	Problem	Language	Result	Execution time	Memory
330722		Mackerel_Pike	Plahte (COCI17_plahte)	C++14	0 / 160	1756 ms	524292 KiB

plahte

#include<bits/stdc++.h>

using namespace std;

#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define PB push_back
#define MP make_pair
#define PH push
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double Lf;
typedef pair<int, int> pii;

const int maxn = 1.5e5 + 5;
const int maxm = 1.5e5 + 5;
const int maxv = maxn + maxm;

int n, m, tot;

class Rectangle{
public:
	ll a, b, c, d;
} rec[maxn];

class Ink{
public:
	ll x, y;
	int k;
} ink[maxm];

class Event{
public:
	ll t;
	int id;
	Event(){}
	Event(ll t_, int id_): t(t_), id(id_){}
	inline bool operator < (const Event &oth)const{
		if(t != oth.t)
			return (t < oth.t);
		int tp1 = (id < 0 ? 2 : (id > n ? 1 : 0)), tp2 = (oth.id < 0 ? 2 : (oth.id > n ? 1 : 0));
		return tp1 < tp2;
	} 
} ;
vector<Event> evn;

int id[maxv], ans[maxn], fa[maxn];
vector<int> vk;
vector<int> g[maxv];
set<pair<pair<ll, ll>, int> > s;
set<int> col[maxv];

inline void insert(int i){
//	printf("insert (%d %d) %d\n", rec[i].b, rec[i].d, i);
	set<pair<pair<ll, ll>, int> >::iterator it = s.lower_bound(MP(MP(rec[i].b, 0), 0));
	if(it == s.begin()){
		s.insert(MP(MP(rec[i].b, rec[i].d), i));
		return;
	}
	--it;
	int j = it -> snd;
	fa[i] = j;
	pair<pair<ll, ll>, int> lit = MP(MP((it -> fst).fst, rec[i].b), it -> snd),
					rit = MP(MP(rec[i].d, (it -> fst).snd), it -> snd);
	s.erase(it);
	s.insert(lit);
	s.insert(rit);
	s.insert(MP(MP(rec[i].b, rec[i].d), i));
	return;
}

inline void erase(int i){
//	printf("erase (%d %d) %d\n", rec[i].b, rec[i].d, i);
	set<pair<pair<ll, ll>, int> >::iterator it = s.lower_bound(MP(MP(rec[i].b, rec[i].d), i));
	if(~fa[i]){
		set<pair<pair<ll, ll>, int> >::iterator lit = it, rit = it;
		--lit, ++rit; 
		pair<pair<ll, ll>, int> nit = MP(MP((lit -> fst).fst, (rit -> fst).snd), fa[i]);
		s.erase(lit), s.erase(rit);
		s.insert(nit);
	}
	s.erase(it);
	return;
}

inline void paint(int i){
//	printf("paint y = %d i = %d\n", ink[i].y, i);
	set<pair<pair<ll, ll>, int> >::iterator it = s.upper_bound(MP(MP(ink[i].y, ink[i].y), 0));
	if(it == s.begin())
		return;
	--it;
	fa[i + n] = (it -> snd);
	return; 
}

inline void merge(int u, int v){
	if(col[id[u]].size() > col[id[v]].size())
		swap(id[u], id[v]);
	for(set<int>::iterator it = col[id[v]].begin(); it != col[id[v]].end(); ++it)
		col[id[u]].insert(*it);
	return;
}

inline void dfs(int u){
	id[u] = tot++;
	if(u > n){
		col[id[u]].insert(ink[u - n].k);
		return;
	}
	FOR(i, 0, g[u].size()){
		int v = g[u][i];
		dfs(v);
		merge(u, v);
	}
	
	ans[u] = col[id[u]].size();
	return;
}

int main(){
//	freopen("b.in", "r", stdin);
//	freopen("b.out", "w", stdout);
	
	scanf("%d%d", &n, &m);
	
	REP(i, 1, n){
		scanf("%lld%lld%lld%lld", &rec[i].a, &rec[i].b, &rec[i].c, &rec[i].d);
		evn.PB(Event(rec[i].a, i));
		evn.PB(Event(rec[i].c, -i));
	}
	
	REP(i, 1, m){
		scanf("%lld%lld%d", &ink[i].x, &ink[i].y, &ink[i].k);
		evn.PB(Event(ink[i].x, n + i));
		vk.PB(ink[i].k);
	}
	
	sort(vk.begin(), vk.end());
	REP(i, 1, m)
		ink[i].k = lower_bound(vk.begin(), vk.end(), ink[i].k) - vk.begin();
	
	sort(evn.begin(), evn.end());
	memset(fa, -1, sizeof(fa));
	
//	FOR(i, 0, evn.size())
//		printf("t = %d id = %d\n", evn[i].t, evn[i].id);
	
	for(int i = 0, j; i < evn.size(); i = j){
		for(j = i; j < evn.size() && evn[j].t == evn[i].t; ++j){
			if(evn[j].id > n)
				paint(evn[j].id - n);
			else if(evn[j].id > 0)
				insert(evn[j].id);
			else
				erase(-evn[j].id);
		}
	}
	
	REP(i, 1, n + m) if(~fa[i])
		g[fa[i]].PB(i);
		
	REP(i, 1, n + m) if(!~fa[i])
		dfs(i);
		
	REP(i, 1, n)
		printf("%d\n", ans[i]);
	return 0;
}

Compilation message (stderr)

plahte.cpp: In function 'void dfs(int)':
plahte.cpp:5:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i, x, y) for(int i = (x); i < (y); ++i)
      |                                         ^
plahte.cpp:113:2: note: in expansion of macro 'FOR'
  113 |  FOR(i, 0, g[u].size()){
      |  ^~~
plahte.cpp: In function 'int main()':
plahte.cpp:151:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |  for(int i = 0, j; i < evn.size(); i = j){
      |                    ~~^~~~~~~~~~~~
plahte.cpp:152:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |   for(j = i; j < evn.size() && evn[j].t == evn[i].t; ++j){
      |              ~~^~~~~~~~~~~~
plahte.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
plahte.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  130 |   scanf("%lld%lld%lld%lld", &rec[i].a, &rec[i].b, &rec[i].c, &rec[i].d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:136:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  136 |   scanf("%lld%lld%d", &ink[i].x, &ink[i].y, &ink[i].k);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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