QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#48683#4393. Snatch Groceriesneko_nyaa#AC ✓72ms10376kbC++20764b2022-09-15 10:05:192022-09-15 10:05:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-15 10:05:22]
  • 评测
  • 测评结果:AC
  • 用时:72ms
  • 内存:10376kb
  • [2022-09-15 10:05:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

bool overlap(pair<int, int> a, pair<int, int> b) {
	auto [l1, r1] = a;
	auto [l2, r2] = b;

	if (l1 > r2) return 0;
	if (l2 > r1) return 0;
	return 1;
}

void solve() {
	int n; cin >> n;
	vector<pair<int, int>> p;
	for (int i = 0; i < n; i++) {
		int l, r; cin >> l >> r;
		p.emplace_back(l, 0);
		p.emplace_back(r, 1);
	}
	sort(p.begin(), p.end());

	int ans = 0;
	int prv = 1;
	for (auto [x, c]: p) {
		if (c != (prv^1)) {
			cout << ans << '\n';
			return;
		} else {
			prv ^= 1;
			ans += prv;
		}
	}
	cout << ans << '\n';
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	int t; cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 72ms
memory: 10376kb

input:

5
3
1 2
3 4
5 6
3
1 2
3 4
4 5
100000
263324740 263324748
920719069 920719077
82595123 82595132
765796214 765796222
621714954 621714959
77799324 77799332
278166427 278166428
375391536 375391545
856576804 856576812
512542774 512542781
829984452 829984457
302442403 302442404
779239984 779239986
1189173...

output:

3
1
275
5575
10000

result:

ok 5 lines