Submission #332297

#	Time	Username	Problem	Language	Result	Execution time	Memory
332297		Mackerel_Pike	Plahte (COCI17_plahte)	C++14	160 / 160	392 ms	61780 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;

class SegmentTree{
private:
	inline void pushDown(int x){
		if(dat[x])
			dat[x << 1] = dat[x << 1 | 1] = dat[x], dat[x] = 0;
		return;
	}
public:
	static const int siz = 1048576;
	int dat[siz << 1];
	inline int size(){ return siz; }
	inline void init(){ memset(dat, -1, sizeof(dat)); }
	inline void update(int x, int l, int r, int s, int t, int k){
		if(l >= s && r <= t){
			dat[x] = k;
			return;
		}
		int md = l + r >> 1;
		pushDown(x);
		if(s <= md)
			update(x << 1, l, md, s, t, k);
		if(t > md)
			update(x << 1 | 1, md + 1, r, s, t, k);
		return;
	}
	inline int query(int x, int l, int r, int y){
		if(l == r)
			return dat[x];
		int md = l + r >> 1;
		pushDown(x);
		if(y <= md)
			return query(x << 1, l, md, y);
		return query(x << 1 | 1, md + 1, r, y);
	}
} seg;

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

inline int pos(ll x){ return lower_bound(vy.begin(), vy.end(), x) - vy.begin(); }

inline void insert(int i){
	int l = pos(rec[i].b), r = pos(rec[i].d);
	int res = seg.query(1, 0, seg.size() - 1, l);
	if(res)
		fa[i] = res;
	seg.update(1, 0, seg.size() - 1, l, r, i);
	return;
}

inline void erase(int i){
	int l = pos(rec[i].b), r = pos(rec[i].d);
	seg.update(1, 0, seg.size() - 1, l, r, fa[i]);
	return;
}

inline void paint(int i){
	int y = pos(ink[i].y);
	int res = seg.query(1, 0, seg.size() - 1, y);
	fa[i + n] = res;
	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));
		vy.PB(rec[i].b);
		vy.PB(rec[i].d);
	}
	
	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));
		vy.PB(ink[i].y);
	}
	
	sort(vy.begin(), vy.end());
	vy.erase(unique(vy.begin(), vy.end()), vy.end());
	
	sort(evn.begin(), evn.end());
	memset(fa, -1, sizeof(fa));
	
	seg.init();
	
	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 member function 'void SegmentTree::update(int, int, int, int, int, int)':
plahte.cpp:67:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |   int md = l + r >> 1;
      |            ~~^~~
plahte.cpp: In member function 'int SegmentTree::query(int, int, int, int)':
plahte.cpp:78:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |   int md = l + r >> 1;
      |            ~~^~~
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:129:2: note: in expansion of macro 'FOR'
  129 |  FOR(i, 0, g[u].size()){
      |  ^~~
plahte.cpp: In function 'int main()':
plahte.cpp:167:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |  for(int i = 0, j; i < evn.size(); i = j){
      |                    ~~^~~~~~~~~~~~
plahte.cpp:168:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |   for(j = i; j < evn.size() && evn[j].t == evn[i].t; ++j){
      |              ~~^~~~~~~~~~~~
plahte.cpp:143:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  143 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
plahte.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  146 |   scanf("%lld%lld%lld%lld", &rec[i].a, &rec[i].b, &rec[i].c, &rec[i].d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:154:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  154 |   scanf("%lld%lld%d", &ink[i].x, &ink[i].y, &ink[i].k);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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