QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#571521 | #9353. Interesting Permutation | real_sigma_team# | RE | 0ms | 0kb | C++23 | 1.2kb | 2024-09-18 00:03:21 | 2024-09-18 00:03:22 |
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