Submission #87363

#	Time	Username	Problem	Language	Result	Execution time	Memory
87363		jasony123123	Plahte (COCI17_plahte)	C++11	0 / 160	2091 ms	364008 KiB

plahte

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.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

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 SZ> struct SegmentTree {
//	stack <pii> data[SZ * 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() == x);
//			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 += offset;
//		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;
//	}
//};
//SegmentTree<1 << 18> tree;

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));
	}
}

/**************/
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;
}
/**************/

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

void merge(set<int> &a, set<int> &b) {
	if (a.size() > b.size()) { // merge b into a
		a.insert(b.begin(), b.end());
	}
	else { // merge a into b then swap
		b.insert(a.begin(), a.end());
		swap(a, b);
	}
}
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];
		if (e.f == -1) { // start
			par[e.id] = query((e.y1 + e.y2) / 2); // parent of e.id
			update(e.y1, e.y2, { e.id, i }); // add id into seg tree
		}
		else if (e.f == 1) { //  end
			ddelete(e.y1, e.y2, { e.id, i });
		}
		else { // ball
			colors[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() {
#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
	freopen("output.out", "w", stdout);
#else
	// online submission
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

Compilation message (stderr)

plahte.cpp: In function 'void io()':
plahte.cpp:226:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("input.in", "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:227:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("output.out", "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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