QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#571522 | #9349. Exchanging Gifts | real_sigma_team# | TL | 0ms | 3576kb | C++23 | 1.2kb | 2024-09-18 00:03:49 | 2024-09-18 00:03:50 |
Judging History
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();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
input:
2 1 1 5 3 3 2 1 3 3 1 3 3 3 2 1 4 2 2 3 3 2 1 2
output:
4 6
result:
ok 2 lines
Test #2:
score: -100
Time Limit Exceeded
input:
10000 100 1 30 371028678 371028678 371028678 716418076 398221499 591504380 398221499 398221499 591504380 777141390 398221499 591504380 591504380 777141390 287847807 716418076 777141390 716418076 777141390 287847807 287847807 287847807 371028678 371028678 398221499 777141390 371028678 6827702 6827702...
output:
700 68 332 284 131 1048 194 667 704 0 484 252 35 351 1228 238 1025 354 383 571 4272 340 1044 199 448 190 0 69 841 546 247 883 138 1633 91 3308 2556 1280 488 618 407 381 383 2865 0 496 1202 53 0 415 662 380 41 18 91 505 818 603 241 764 1227 1802 176 187 817 1489 460 296 238 236 1028 0 606 1696 746 10...