Submission #87456

#	Time	Username	Problem	Language	Result	Execution time	Memory
87456		jasony123123	Plahte (COCI17_plahte)	C++11	160 / 160	1263 ms	379484 KiB

plahte

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define vsort(a) sort(a.begin(), a.end());
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define MAXN 80010
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void io();

template <int K> struct SegmentTree {
	int SZ = 1 << K;
	/**/
	stack <pii> data[(1 << K) * 2]; // <id, time>
	void update(int a, int b, pii x) { // add x to [a,b]
		update(1, 0, SZ - 1, a, b, x);
	}
	void update(int node, int l, int r, int a, int b, pii x) {
		if (l > b || r < a) return;
		if (l >= a && r <= b) {
			data[node].push(x);
			return;
		}
		int mid = (l + r) / 2;
		update(node * 2, l, mid, a, b, x);
		update(node * 2 + 1, mid + 1, r, a, b, x);
	}
	void ddelete(int a, int b, pii x) {
		ddelete(1, 0, SZ - 1, a, b, x);
	}
	void ddelete(int node, int l, int r, int a, int b, pii x) {
		if (l > b || r < a) return;
		if (l >= a && r <= b) {
		//	assert(data[node].top().first == x.first);
			data[node].pop();
			return;
		}
		int mid = (l + r) / 2;
		ddelete(node * 2, l, mid, a, b, x);
		ddelete(node * 2 + 1, mid + 1, r, a, b, x);
	}
	int query(int node) {
		node += SZ;
		pii ret = { -1,-1 }; // id, time

		while (node) {
			if (!data[node].empty()) {
				if (data[node].top().second > ret.second) {
					ret = data[node].top();
				}
			}
			node /= 2;
		}
		return ret.first;
	}
	/**/

	/**
	stack<pii> fakeSeg[100000]; // <id, time>
	void update(int a, int b, pii x) { // add x to [a,b]
		FORE(i, a, b)
			fakeSeg[i].push(x);
	}
	
	void ddelete(int a, int b, pii x) {
		FORE(i, a, b) {
			assert(fakeSeg[i].top().first == x.first);
			fakeSeg[i].pop();
		}
	}
	int query(int node) {
		if (fakeSeg[node].size() == 0)
			return -1;
		return fakeSeg[node].top().first;
	}
	/**/
};
SegmentTree<18> tree;
/**
int main() {
	io();
	int N;
	cin >> N;
	FOR(i, 0, N) {
		int type;
		cin >> type;
		if (type == 0) { // add
			int a, b, x;
			cin >> a >> b >> x;
			tree.update(a, b, { x,i });
		}
		else if (type == 1) { // remove
			int a, b, x;
			cin >> a >> b >> x;
			tree.ddelete(a, b, { x,i });
		}
		else { // query
			int a;
			cin >> a;
			cout << tree.query(a) << "\n";
		}
	}
}
/**/


struct Event {
	int x, f, y1, y2, id;
	Event(int a, int b, int c, int d, int e) : x(a), f(b), y1(c), y2(d), id(e) {}
	bool operator< (const Event& other) const {
		return mp(x, f) < mp(other.x, other.f);
	}
};
int N, M; // rect, balls
v<Event> allevents;

void compressCoord() {
	map<int, int> conv;
	FOR(i, 0, allevents.size()) {
		conv[allevents[i].y1] = 0;
		conv[allevents[i].y2] = 0;
	}
	int num = 0;
	for (auto& en : conv)
		en.second = num++;
	FOR(i, 0, allevents.size()) {
		allevents[i].y1 = conv[allevents[i].y1];
		allevents[i].y2 = conv[allevents[i].y2];
	}
}

void input() {
	cin >> N >> M;
	allevents.push_back(Event(-1, -1, -1, 1000000001, 0)); // start
	allevents.push_back(Event(1000000001, 1, -1, 1000000001, 0)); // end
	FOR(i, 0, N) {
		int x1, y1, x2, y2, id = i + 1;
		cin >> x1 >> y1 >> x2 >> y2;
		allevents.push_back(Event(x1, -1, y1, y2, id)); // start
		allevents.push_back(Event(x2, 1, y1, y2, id)); // end
	}
	FOR(i, 0, M) {
		int x, y, c;
		cin >> x >> y >> c;
		allevents.push_back(Event(x, 0, y, -1, c));
	}
}

int par[MAXN];
v<int> adj[MAXN];
set<int> colors[MAXN];
int ans[MAXN];

void merge(set<int> &a, set<int> &b) {
	if (a.size() > b.size()) { // merge b into a
		a.insert(b.begin(), b.end());
		b.clear();
	}
	else { // merge a into b then swap
		b.insert(a.begin(), a.end());
		swap(a, b);
		b.clear();
	}
}
void dfs(int cur, int par) {
	for (int chi : adj[cur]) if (chi != par) {
		dfs(chi, cur);
		merge(colors[cur], colors[chi]);
	}
	ans[cur] = colors[cur].size();
}

int main() {
	io();
	input();
	compressCoord();
	vsort(allevents);

	FOR(i, 0, allevents.size()) {
		Event e = allevents[i];
		//		cout << "lol\n";
		if (e.f == -1) { // start
			par[e.id] = tree.query((e.y1 + e.y2) / 2); // parent of e.id
			tree.update(e.y1, e.y2, { e.id, i }); // add id into seg tree
		}
		else if (e.f == 1) { //  end
			tree.ddelete(e.y1, e.y2, { e.id, i });
		}
		else { // ball
			colors[tree.query(e.y1)].insert(e.id); // which id is this ball in?
		}
	}

/*	FORE(i, 0, N)
		cout << i << ": " << par[i] << " par\n";
	FORE(i, 0, N) {
		cout << i << "contains: ";
		for (int c : colors[i])
			cout << c << " ";
		cout << "\n";
	}*/

	FORE(i, 0, N) {
		if (par[i] != -1) {
			adj[par[i]].push_back(i);
			adj[i].push_back(par[i]);
		}
	}

	dfs(0, -1);
	FORE(i, 1, N)
		cout << ans[i] << "\n";
	return 0;
}
/**/

void io() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

Compilation message (stderr)

plahte.cpp:90:2: warning: "/*" within comment [-Wcomment]
  /**/
   
plahte.cpp:118:1: warning: "/*" within comment [-Wcomment]
 /**/

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