oj.uz

Submission #880613

# Submission time Handle Problem Language Result Execution time Memory
880613 2023-11-29T17:30:34 Z serifefedartar Plahte (COCI17_plahte) C++17
160 / 160
 370 ms 92816 KB 
#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll LOGN = 21;
const ll MAXN = 400000;

struct Rect {
	int a, b, c, d;
	Rect() { }
	Rect(int _a, int _b, int _c, int _d) : a(_a), b(_b), c(_c), d(_d) { }
};

vector<Rect> R;
vector<pair<pair<int,int>,int>> v;
int sg[4*MAXN], lazy[4*MAXN], par[MAXN], res[MAXN];
bool vis[MAXN];
vector<int> in[MAXN], out[MAXN], query[MAXN];
vector<int> ccX, ccY;
set<int> st[MAXN];

int indexX(int k) {
	return upper_bound(ccX.begin(), ccX.end(), k) - ccX.begin();
}

int indexY(int k) {
	return upper_bound(ccY.begin(), ccY.end(), k) - ccY.begin();
}

void push(int k, int a, int b) {
	if (lazy[k] != -2) {
		sg[k] = lazy[k];
		if (a != b) {
			lazy[2*k] = lazy[k];
			lazy[2*k+1] = lazy[k];
		}
		lazy[k] = -2;
	}
}

void update(int k, int a, int b, int q_l, int q_r, int val) {
	push(k, a, b);
	if (q_r < a || q_l > b)
		return ;
	if (q_l <= a && b <= q_r) {
		lazy[k] = val;
		push(k, a, b);
		return ;
	}
	update(2*k, a, (a+b)/2, q_l, q_r, val);
	update(2*k+1, (a+b)/2+1, b, q_l, q_r, val);
	sg[k] = max(sg[2*k], sg[2*k+1]);
}

int qry(int k, int a, int b, int q_l, int q_r) {
	push(k, a, b);
	if (b < q_l || a > q_r) 
		return -1;
	if (q_l <= a && b <= q_r)
		return sg[k];

	int Q1 = qry(2*k, a, (a+b)/2, q_l, q_r);
	int Q2 = qry(2*k+1, (a+b)/2+1, b, q_l, q_r);
	return max(Q1, Q2);
}

vector<vector<int>> graph;
void dfs(int node) {
	if (vis[node])
		return ;
	vis[node] = true;

	for (auto u : graph[node]) {
		dfs(u);
		if (st[node].size() < st[u].size())
			swap(st[node], st[u]);	
		for (auto v : st[u])
			st[node].insert(v);
	}
	res[node] = st[node].size();
}

int main() {
	fast
	for (int i = 0; i < 4*MAXN; i++)
		lazy[i] = -2;
	memset(sg, -1, sizeof(sg));
	memset(par, -1, sizeof(par));
	int N, M;
	cin >> N >> M;

	graph = vector<vector<int>>(N+1, vector<int>());
	R.push_back(Rect());
	v.push_back({{-1, -1}, -1});
	for (int i = 1; i <= N; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		R.push_back(Rect(a, b, c, d));
		ccX.push_back(a);
		ccX.push_back(c);
		ccY.push_back(b);
		ccY.push_back(d);
	}
	for (int i = 1; i <= M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v.push_back({{a, b}, c});
		ccX.push_back(a);
		ccY.push_back(b);
	}
	sort(ccX.begin(), ccX.end());
	sort(ccY.begin(), ccY.end());
	ccX.erase(unique(ccX.begin(), ccX.end()), ccX.end());
	ccY.erase(unique(ccY.begin(), ccY.end()), ccY.end());

	for (int i = 1; i <= N; i++) {
		in[indexX(R[i].a)].push_back(i);
		out[indexX(R[i].c)].push_back(i);
	}
	for (int i = 1; i <= M; i++)
		query[indexX(v[i].f.f)].push_back(i);

	int n = ccY.size();
	for (int i = 0; i < MAXN; i++) {
		for (auto u : in[i]) {
			par[u] = qry(1, 1, n, indexY(R[u].b), indexY(R[u].d));
			if (par[u] != -1)
				graph[par[u]].push_back(u);
			update(1, 1, n, indexY(R[u].b), indexY(R[u].d), u);
		}

		for (auto u : query[i]) {
			int where = qry(1, 1, n, indexY(v[u].f.s), indexY(v[u].f.s));
			if (where != -1)
				st[where].insert(v[u].s);
		}

		for (auto u : out[i])
			update(1, 1, n, indexY(R[u].b), indexY(R[u].d), par[u]);
	}

	for (int i = 1; i <= N; i++) {
		if (!vis[i])
			dfs(i);
	}

	for (int i = 1; i <= N; i++)
		cout << res[i] << "\n";
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 72080 KB Output is correct
2 Correct 108 ms 72708 KB Output is correct
3 Correct 14 ms 63324 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 73772 KB Output is correct
2 Correct 137 ms 72980 KB Output is correct
3 Correct 14 ms 63320 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 81504 KB Output is correct
2 Correct 209 ms 79020 KB Output is correct
3 Correct 14 ms 63320 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 92816 KB Output is correct
2 Correct 370 ms 89748 KB Output is correct
3 Correct 16 ms 63480 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 91436 KB Output is correct
2 Correct 339 ms 88000 KB Output is correct
3 Correct 14 ms 63320 KB Output is correct