Submission #1167383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167383		akacool445k	Cat Exercise (JOI23_ho_t4)	C++20	41 / 100	62 ms	10636 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define int long long
#define pint pair<int, int>
#define vint vector<int>
const int mod = 1e9 + 7;
const int mxn = 2e5 + 5;
const int say = INT_MAX / 2;
const int gex = INT_MIN / 2;

const long long oo = 1e18;
int p[mxn], pos[4 * mxn];
int n;
int build(int id, int L, int R) {
	if(L == R) {
		pos[id] = L;
		return L;
	}
	int M = (L + R) / 2, x = 2 * id + 1, y = x + 1;
	int aa = build(x, L, M);
	int bb = build(y, M + 1, R);
	if(p[aa] > p[bb]) {
		pos[id] = aa;
		return aa;
	} else {
		pos[id] = bb;
		return bb;
	}
}

int query(int id, int L, int R, int l, int r) {
	if(L == l && r == R) {
		return pos[id];
	}
	int M = (L + R) / 2, x = 2 * id + 1, y = x + 1;
	if(r <= M) return query(x, L, M, l, r);
	if(l > M) return query(y, M + 1, R, l, r);
	int aa = query(x, L, M, l, M);
	int bb = query(y, M + 1, R, M + 1, r);
	if(p[aa] > p[bb]) return aa;
	else return bb;
}

bool vis[mxn];
int dep[mxn];
void dfs(int l, int r, int par) {
	// cout << "hi";
	if(l > r || l < 0 || r > n) return;
	if(l == r) {
		dep[l] = dep[par] + 1;
		return;
	}
	int id = query(0, 0, n - 1, l, r);
	if(par == -1) dep[id] = 0;
	else dep[id] = dep[par] + abs(par - id);
	dfs(id + 1, r, id);
	dfs(l, id - 1, id);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
	cout.tie(0);
	cin >> n;
	// int p[n];
	for(int i = 0; i < n; i++) cin >> p[i];
	for(int i = 0; i < n - 1; i++) {
		int x, y;
		cin >> x >> y;
	}
	build(0, 0, n - 1);
	dfs(0, n - 1, -1);
	int ans = 0;
	for(int i = 0; i < n; i++) {
		ans = max(ans, dep[i]);
		// cout << dep[i] << ' ';
	}
	// cout << '\n';
	cout << ans << '\n';
	// int q; cin >> q;
	// while(q--) {
	// 	int l, r; cin >> l >> r;
	// 	cout << query(0, 0, n - 1, l , r) << '\n';
	// }
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26