oj.uz

Submission #238188

# Submission time Handle Problem Language Result Execution time Memory
238188 2020-06-10T07:01:46 Z Mlxa Plahte (COCI17_plahte) C++14
160 / 160
 461 ms 87084 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define x first
#define y second
#define mp make_pair
#define mt make_tuple

const int N     = 1 << 19;
const int INF   = 0x3f3f3f3f;
const int OPEN  = 0;
const int QUERY = 1;
const int CLOSE = 2;

struct event {
	int x;
	int yl;
	int yr;
	int i;  // index / color
	int tp; // 0 - open, 1 - query, 2 - close
	event(int a, int b, int c, int d, int e) : x(a), yl(b), yr(c), i(d), tp(e) {}
};

bool operator<(event a, event b) {
	return tie(a.x, a.tp) < tie(b.x, b.tp);
}

int n;
int m;

vector<event> line;
vector<int> g[N];
vector<int> roots;
vector<int> srt;
vector<int> tree[2 * N];
int len[N];

void add(event e) {
	len[e.i] = e.yr - e.yl;
	for (int l = e.yl + N, r = e.yr + N; l <= r; l /= 2, r /= 2) {
		if (l % 2 == 1) {
			tree[l++].push_back(e.i);
		}
		if (r % 2 == 0) {
			tree[r--].push_back(e.i);
		}
	}
}

void pop(vector<int> &vec, int val) {
	assert(vec.size() && vec.back() == val);
	vec.pop_back();
}

void del(event e) {
	for (int l = e.yl + N, r = e.yr + N; l <= r; l /= 2, r /= 2) {
		if (l % 2 == 1) {
			pop(tree[l++], e.i);
		}
		if (r % 2 == 0) {
			pop(tree[r--], e.i);
		}
	}
}

int query(int i) {
	int res = -1;
	for (i += N; i > 0; i /= 2) {
		if (tree[i].empty()) {
			continue;
		}
		int cur = tree[i].back();
		if (res == -1 || len[res] > len[cur]) {
			res = cur;
		}
	}
	return res;
}

set<int> col[N];
int ans[N];

void solve(int v) {
	for (int u : g[v]) {
		solve(u);
		if (col[v].size() < col[u].size()) {
			swap(col[v], col[u]);
		}
		col[v].insert(all(col[u]));
		col[u].clear();
	}
	ans[v] = (int)col[v].size();
}

signed main() {
#ifdef LC
	assert(freopen("input.txt", "r", stdin));
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for (int a, b, c, d, i = 0; i < n; ++i) {
		cin >> a >> b >> c >> d;
		line.emplace_back(a, b, d, i, OPEN);
		line.emplace_back(c, b, d, i, CLOSE);
		srt.push_back(b);
		srt.push_back(d);
	}
	for (int x, y, k, i = 0; i < m; ++i) {
		cin >> x >> y >> k;
		line.emplace_back(x, y, y, k, QUERY);
		srt.push_back(y);
	}
	sort(all(line));
	sort(all(srt));
	for (event ev : line) {
		ev.yl = lower_bound(all(srt), ev.yl) - srt.begin();
		ev.yr = lower_bound(all(srt), ev.yr) - srt.begin();
		int par = query((ev.yl + ev.yr) / 2);
		if (ev.tp == OPEN) {
			if (par == -1) {
				roots.push_back(ev.i);
			} else {
				g[par].push_back(ev.i);
			}
			add(ev);
		} else if (ev.tp == CLOSE) {
			del(ev);
		} else {
			assert(ev.tp == QUERY);
			if (par != -1) {
				col[par].insert(ev.i);
			}
		}
	}

	for (int v : roots) {
		solve(v);
	}

	for (int i = 0; i < n; ++i) {
		cout << ans[i] << "\n";
	}
	return 0;
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 67172 KB Output is correct
2 Correct 136 ms 66836 KB Output is correct
3 Correct 44 ms 61848 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 70148 KB Output is correct
2 Correct 178 ms 68740 KB Output is correct
3 Correct 37 ms 62080 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 77432 KB Output is correct
2 Correct 248 ms 72696 KB Output is correct
3 Correct 38 ms 61944 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 87084 KB Output is correct
2 Correct 461 ms 83576 KB Output is correct
3 Correct 38 ms 61944 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 84476 KB Output is correct
2 Correct 436 ms 83324 KB Output is correct
3 Correct 38 ms 61952 KB Output is correct