QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#616865#6308. MagicfryanTL 2258ms11440kbC++23994b2024-10-06 12:41:572024-10-06 12:41:58

Judging History

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

  • [2024-10-06 12:41:58]
  • 评测
  • 测评结果:TL
  • 用时:2258ms
  • 内存:11440kb
  • [2024-10-06 12:41:57]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
#define int int64_t
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

const int mxn = 1e4+5;

int n;
array<int,2> iv[mxn];
vector<int> adj[mxn];
int used[mxn];
int mt[mxn];

bool kuhn(int v) {
	if (used[v]) return 0;
	used[v] = 1;
	for (int u : adj[v]) {
		if (mt[u]==-1 || kuhn(mt[u])) {
			mt[u] = v;
			return 1;
		}
	}
	return 0;
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	cin>>n;
	
	for (int i=0; i<n; i++) {
		cin>>iv[i][0]>>iv[i][1];
	}
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			if (iv[i][0] < iv[j][0] && iv[i][1] > iv[j][0] && iv[j][1] > iv[i][1]) {
				adj[iv[j][0]].push_back(iv[i][1]);
			}
		}
	}
	n *= 2;
	
	memset(mt,-1,sizeof(mt));
	for (int v=0; v<n; v++) {
		memset(used,0,sizeof(used));
		kuhn(v);
	}
	
	int cnt = n;
	
	for (int i=0; i<n; i++) {
		if (mt[i] != -1) {
			cnt--;
		}
	}
	
	cout<<cnt;
	
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3756kb

input:

5
2 3
6 7
1 9
5 10
4 8

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 82ms
memory: 4124kb

input:

5000
7985 7987
42 46
1591 1593
407 410
6305 6306
1456 1457
5874 5875
7135 7137
7041 7046
6813 6815
8868 8871
665 666
4055 4056
9789 9796
7067 7068
4745 4746
5167 5171
1735 1737
2125 2128
1444 1447
1348 1352
6087 6090
1381 1384
1600 1601
5187 5190
2801 2802
8449 8450
9376 9377
4021 4024
2674 2676
490...

output:

8134

result:

ok 1 number(s): "8134"

Test #3:

score: 0
Accepted
time: 82ms
memory: 4192kb

input:

5000
3171 3172
4062 4064
4647 4651
3670 3673
7112 7114
9714 9717
3781 3789
8422 8426
457 460
5450 5454
7113 7122
6313 6320
9969 9973
828 832
6878 6892
4476 4483
892 903
251 259
6304 6315
130 134
9206 9215
2679 2686
9090 9091
8222 8228
9374 9375
2985 2989
3397 3401
4916 4918
6819 6821
883 889
2516 25...

output:

7047

result:

ok 1 number(s): "7047"

Test #4:

score: 0
Accepted
time: 85ms
memory: 4244kb

input:

5000
7269 7286
1979 1990
4225 4241
7866 7872
2052 2067
1508 1514
2366 2370
3488 3493
8979 8987
302 306
6730 6732
7704 7705
5528 5544
7420 7425
4705 4712
593 601
6662 6668
5228 5257
2008 2013
548 562
7949 7950
1017 1020
1025 1028
6 11
4722 4736
9945 9950
8368 8379
6781 6787
4558 4566
400 404
858 864
...

output:

6191

result:

ok 1 number(s): "6191"

Test #5:

score: 0
Accepted
time: 84ms
memory: 4524kb

input:

5000
3005 3008
7811 7821
2832 2840
9812 9818
3947 3952
3629 3665
7443 7455
1473 1478
1467 1494
5499 5508
229 232
9477 9498
9500 9514
4769 4775
9488 9503
1514 1520
5101 5112
2455 2456
3558 3610
9072 9188
659 666
2286 2301
9735 9782
5959 5984
5823 5844
1827 1835
3658 3681
3494 3503
1016 1018
3418 3420...

output:

5636

result:

ok 1 number(s): "5636"

Test #6:

score: 0
Accepted
time: 106ms
memory: 4996kb

input:

5000
1017 1019
5731 5744
8592 8697
3414 3561
277 356
4421 4458
7969 7989
3733 3759
1975 1986
6895 6898
8580 8657
2320 2325
6494 6510
3574 3616
7721 7780
7756 7835
1744 1748
5085 5102
5428 5588
6823 6847
9348 9405
1969 2064
1152 1242
3676 3679
5569 5713
213 248
8277 8285
3739 3782
5582 5604
9076 9105...

output:

5225

result:

ok 1 number(s): "5225"

Test #7:

score: 0
Accepted
time: 661ms
memory: 5804kb

input:

5000
4269 4768
7697 7804
4289 4316
6641 6742
3782 3871
9785 9858
1845 1979
6300 6412
8194 8616
3 18
8536 8790
7 129
4406 4448
3556 3609
2800 2918
3081 3164
1854 1948
8220 8546
7070 7318
1117 1195
8770 8944
5754 5760
8512 8590
5714 5829
6132 6156
8252 8381
889 1149
1899 1949
4675 4683
4282 4426
2977 ...

output:

5124

result:

ok 1 number(s): "5124"

Test #8:

score: 0
Accepted
time: 1134ms
memory: 7492kb

input:

5000
1247 1337
3192 3474
7887 8008
2912 3065
4356 4573
9268 9376
987 1165
6972 7155
580 668
331 718
455 640
4815 4854
3783 3988
8426 8579
7459 7563
1991 2482
9585 9973
7562 7627
7472 8428
86 320
8319 8331
8596 8953
5729 6468
7209 7364
1026 1246
6575 6608
5048 5050
1957 2531
9408 9489
3092 3096
845 1...

output:

5079

result:

ok 1 number(s): "5079"

Test #9:

score: 0
Accepted
time: 2258ms
memory: 11440kb

input:

5000
1356 3126
3141 3369
3524 4274
1330 1812
4781 5129
2713 2743
139 741
1978 2219
1841 3301
6951 7599
7003 8073
6492 6563
9044 9185
7533 7745
9596 9862
2807 3582
4284 4486
3483 4771
7683 8441
1677 2359
4700 4752
861 2053
701 1098
1283 2450
1997 2270
6794 7284
9469 9496
280 731
1125 1683
2283 2539
3...

output:

5059

result:

ok 1 number(s): "5059"

Test #10:

score: -100
Time Limit Exceeded

input:

5000
3676 4155
4813 4957
6926 7118
6695 6826
3624 3847
1696 2051
5628 7796
1145 2640
244 803
3089 3246
101 2013
7644 8249
6252 9848
3352 5216
1683 2490
114 1135
2868 3037
3516 4495
4122 5522
2488 3785
138 579
4716 5036
2918 4052
491 712
2751 4533
56 495
2085 3038
6523 6768
5592 6555
6040 6965
9716 9...

output:


result: