Submission #87369

#	Time	Username	Problem	Language	Result	Execution time	Memory
87369		jasony123123	Plahte (COCI17_plahte)	C++11	0 / 160	1112 ms	315236 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().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;
	}
};
SegmentTree<100000> 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] = 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() {
#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