oj.uz

Submission #138875

# Submission time Handle Problem Language Result Execution time Memory
138875 2019-07-30T16:31:44 Z KCSC Plahte (COCI17_plahte) C++14
160 / 160
 864 ms 73408 KB 
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define REP(i, n) for (int i = 0; i < int(n); ++i)
#define ALL(x) (x).begin(), (x).end()

const int DIM = 250005;

struct Event {
	int a, b, c, d;
}; vector<Event> events;

vector<pair<int, int>> segTree[DIM * 4];
set<int> colorSet[DIM]; 
vector<int> posList, graph[DIM];

int answer[DIM], whatSet[DIM];

inline bool cmp(Event &e1, Event &e2) {
	if (e1.b != e2.b)
		return e1.b < e2.b;
	return e1.a < e2.a;
}

void update(int nd, int le, int ri, int st, int en, pair<int, int> vl) {
	if (st <= le and ri <= en) {
		if (vl.first == -2)
			segTree[nd].pop_back();
		else
			segTree[nd].push_back(vl);
	} else {
		int md = (le + ri) / 2;
		if (st <= md)
			update(nd * 2, le, md, st, en, vl);
		if (md < en)
			update(nd * 2 + 1, md + 1, ri, st, en, vl);
	}
}

pair<int, int> query(int nd, int le, int ri, int ps) {
	if (le == ri) {
		if (segTree[nd].empty())
			return make_pair(-2, -2);
		else
			return segTree[nd].back();
	} else {
		pair<int, int> aux;
		int md = (le + ri) / 2;
		if (ps <= md)
			aux = query(nd * 2, le, md, ps);
		else
			aux = query(nd * 2 + 1, md + 1, ri, ps);
		if (segTree[nd].empty())
			return aux;
		else if (aux.first < segTree[nd].back().first)
			return segTree[nd].back();
		else
			return aux;
	}
}

void merge(int a, int b) {
	if (colorSet[whatSet[a]].size() > colorSet[whatSet[b]].size()) 
		swap(a, b);
	for (int x : colorSet[whatSet[a]])
		colorSet[whatSet[b]].insert(x);
	whatSet[a] = whatSet[b];
}

void dfs(int x) {
	int sz = -1, ps = -1;
	for (int y : graph[x]) {
		dfs(y);
		merge(x, y);
	}
	answer[x] = colorSet[whatSet[x]].size();
}

int main(void) {
#ifdef HOME
	freopen("plahte.in", "r", stdin);
	freopen("plahte.out", "w", stdout);
#endif
	int n, m;
	cin >> n >> m;
	static int LIM = 2 * n + m;
	REP(i, n) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		events.push_back({i, x1, y1, y2});
		events.push_back({-1, x2 + 1, y1, y2});
		posList.push_back(y1);
		posList.push_back(y2);
	}
	REP(i, m) {
		int x, y, c;
		cin >> x >>	y >> c;
		events.push_back({LIM, x, y, c});
		posList.push_back(y);
	}
	events.push_back({n, -1, 0, LIM});
	sort(posList.begin(), posList.end());
	sort(events.begin(), events.end(), cmp);
	posList.erase(unique(ALL(posList)), posList.end());
	for (Event &e : events) {
		if (e.a != n) {
			e.c = lower_bound(ALL(posList), e.c) - posList.begin();
			if (e.a != LIM)
				e.d = lower_bound(ALL(posList), e.d) - posList.begin();
		}
		if (e.a == -1) 
			update(1, 0, LIM, e.c, e.d, make_pair(-2, -2));
		else if (e.a < LIM) {
			graph[query(1, 0, LIM, e.c).second].push_back(e.a);
			update(1, 0, LIM, e.c, e.d, make_pair(e.b, e.a));
		} else 
			colorSet[query(1, 0, LIM, e.c).second].insert(e.d);
	}
	REP(i, n + 1) 
		whatSet[i] = i;
	dfs(n);
	REP(i, n)
		cout << answer[i] << "\n";
	return 0;
}

Compilation message

plahte.cpp: In function 'void dfs(int)':
plahte.cpp:72:6: warning: unused variable 'sz' [-Wunused-variable]
  int sz = -1, ps = -1;
      ^~
plahte.cpp:72:15: warning: unused variable 'ps' [-Wunused-variable]
  int sz = -1, ps = -1;
               ^~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 49472 KB Output is correct
2 Correct 267 ms 50024 KB Output is correct
3 Correct 41 ms 41464 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 52016 KB Output is correct
2 Correct 302 ms 51056 KB Output is correct
3 Correct 40 ms 41464 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 61304 KB Output is correct
2 Correct 491 ms 56572 KB Output is correct
3 Correct 39 ms 41464 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 804 ms 73408 KB Output is correct
2 Correct 828 ms 66548 KB Output is correct
3 Correct 41 ms 41464 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 864 ms 70816 KB Output is correct
2 Correct 795 ms 65280 KB Output is correct
3 Correct 41 ms 41464 KB Output is correct