QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#571521#9353. Interesting Permutationreal_sigma_team#RE 0ms0kbC++231.2kb2024-09-18 00:03:212024-09-18 00:03:22

Judging History

你现在查看的是最新测评结果

  • [2024-09-18 00:03:22]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-09-18 00:03:21]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MAXC = 1'000'000'000'000'000'000;

ll get_col(ll l, ll r, vector<pair<ll, vector<ll>>>& all) {
	vector<ll> nc;
	for (auto[t, es] : all) {
		if (t == 1) {
			ll ncol = 0;
			for (auto i : es) {
				ncol += (l <= i) && (i <= r);
			}
			nc.push_back(ncol);
		} else {
			nc.push_back(nc[es[0]] + nc[es[1]]);
		}
	}
	return nc.back();
}

void solve() {
	ll n;
	cin >> n;
	vector<pair<ll, vector<ll>>> arr(n);
	for (ll i = 0; i < n; i++) {
		ll t;
		cin >> t;
		arr[i].first = t;
		if (t == 1) {
			ll k;
			cin >> k;
			for (ll j = 0; j < k; j++) {
				ll x;
				cin >> x;
				arr[i].second.push_back(x);
			}
		} else {
			ll a, b;
			cin >> a >> b;
			a--;
			b--;
			arr[i].second.push_back(a);
			arr[i].second.push_back(b);
		}
	}
	ll ac = get_col(0, MAXC, arr);
	ll l = 0, r = MAXC;
	while (r - l > 1) {
		ll mid = (l + r) / 2;
		if (get_col(0, mid, arr) * 2 < ac) {
			l = mid;
		} else {
			r = mid;
		}
	}
	ll cl = get_col(r, r, arr);
	cout << min(ac, (ac - cl) * 2) << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t;
	cin >> t;
	while (t--) {
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

3
3
0 2 2
3
0 1 2
3
0 2 3

output:


result: