QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#571522#9349. Exchanging Giftsreal_sigma_team#TL 0ms3576kbC++231.2kb2024-09-18 00:03:492024-09-18 00:03:50

Judging History

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

  • [2024-09-18 00:03:50]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3576kb
  • [2024-09-18 00:03:49]
  • 提交

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...

result: