Submission #1155725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155725		blackslex	September (APIO24_september)	C++20	45 / 100	338 ms	16120 KiB

september

#include "september.h"
#include <vector>
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

struct segment {
	int t[N * 4];
	void upd (int l, int r, int idx, int pos, int val) {
		if (l == r) return void(t[idx] = max(t[idx], val));
		int mid = (l + r) >> 1;
		if (pos <= mid) upd(l, mid, idx * 2 + 1, pos, val);
		else upd(mid + 1, r, idx * 2 + 2, pos, val);
		t[idx] = max(t[idx * 2 + 1], t[idx * 2 + 2]);
	}
	int qr (int l, int r, int idx, int tl, int tr) {
		if (l > tr || r < tl) return 0;
		if (l >= tl && r <= tr) return t[idx];
		int mid = (l + r) >> 1;
		return max(qr(l, mid, idx * 2 + 1, tl, tr), qr(mid + 1, r, idx * 2 + 2, tl, tr));
	}
};

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
	int n = N, m = M;
	vector<vector<int>> v(n, vector<int>());
	vector<vector<int>> pos(m, vector<int>(n));
	vector<vector<int>> rpos(m, vector<int>(n));
	vector<segment> segm(m);
	int t = -1;
	for (int i = 1; i < n; i++) {
		v[F[i]].emplace_back(i);
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n - 1; j++) {
			pos[i][S[i][j]] = j;
		}
	}
	auto dfs = [&] (auto &&dfs, int cur, int par) -> void {
		for (auto &e: v[cur]) {
			if (par == e) continue;
			dfs(dfs, e, cur);
			for (int i = 0; i < m; i++) {
				pos[i][cur] = max(pos[i][cur], pos[i][e]);
			}
		}
	};
	dfs(dfs, 0, -1);
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n - 1; j++) {
			segm[i].upd(0, n - 2, 0, j, pos[i][S[i][j]]);
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = n - 2; j >= 0; j--) {
			rpos[i][j] = segm[i].qr(0, n - 2, 0, j, pos[i][S[i][j]]);
			segm[i].upd(0, n - 2, 0, j, rpos[i][j]);
		}
	}
	int ans = 0;
	vector<int> ptr(m);
	for (int i = 0; ; i++) {
		int mx = -1;
		for (int j = 0; j < m; j++) {
			mx = max(mx, rpos[j][ptr[j]]);
		}
		for (int j = 0; j < m; j++) {
			ptr[j] = mx + 1;
		}
		ans++;
		if (mx + 1 >= n - 1) break;
	}
	return ans;
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 14
• Subtask 3: 5 / 5
• Subtask 4: 9 / 9
• Subtask 5: 0 / 5
• Subtask 6: 0 / 11
• Subtask 7: 9 / 9
• Subtask 8: 11 / 11
• Subtask 9: 0 / 9
• Subtask 10: 0 / 16