QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#108318#6308. MagiczqyyyTL 2911ms7212kbC++17746b2023-05-24 15:01:332023-05-24 15:01:35

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-24 15:01:35]
  • 评测
  • 测评结果:TL
  • 用时:2911ms
  • 内存:7212kb
  • [2023-05-24 15:01:33]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=5007;
int n, mat[N]; bool vis[N];
struct seg {int l, r;} a[N];
bitset<N> bs[N];
bool dfs(int x) {
	for (int i=bs[x]._Find_first(); i<=n; i=bs[x]._Find_next(i))
		if (!vis[i]) {
			vis[i]=true;
			if (!mat[i] || dfs(mat[i])) return mat[i]=x, true;
		}
	return false;
}
int main() {
	scanf("%d", &n);
	for (int i=1; i<=n; i++) scanf("%d%d", &a[i].l, &a[i].r);
	sort(a+1, a+n+1, [&](auto x, auto y) {return x.l<y.l;});
	for (int i=1; i<=n; i++)
		for (int j=i+1; j<=n; j++) {
			if (a[i].r<a[j].l) break;
			if (a[i].r<a[j].r) bs[i].set(j);
		}
	int ans=2*n;
	for (int i=1; i<=n; i++)
		fill(vis+1, vis+n+1, false), ans-=dfs(i);
	printf("%d\n", ans);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3620kb

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: 0ms
memory: 6648kb

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: 0ms
memory: 6744kb

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: 3ms
memory: 6692kb

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: 10ms
memory: 6752kb

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: 396ms
memory: 6716kb

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: 97ms
memory: 6844kb

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: 446ms
memory: 6944kb

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: 935ms
memory: 6964kb

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: 0
Accepted
time: 1569ms
memory: 7020kb

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:

5061

result:

ok 1 number(s): "5061"

Test #11:

score: 0
Accepted
time: 2165ms
memory: 7192kb

input:

5000
7645 8814
2855 4135
5584 7079
3371 3514
4858 6115
1160 2738
1016 1244
1090 2532
5407 5453
1272 2001
2660 3153
6849 7796
8127 9419
2827 4055
4303 6893
4269 7945
4804 5316
6680 8387
3561 3848
984 4841
1385 1638
8101 8830
453 9062
6072 9218
3304 3615
8899 9596
4525 4750
481 4112
2187 4061
8254 876...

output:

5077

result:

ok 1 number(s): "5077"

Test #12:

score: 0
Accepted
time: 2670ms
memory: 7012kb

input:

5000
4947 5073
6010 6191
503 3970
4578 5766
5622 9195
7180 7616
2542 6653
1807 7852
6760 7614
612 8136
1166 3586
3157 6433
1032 2855
988 6736
4858 8152
319 2208
6507 9016
7803 9346
773 8940
3646 5774
2504 9762
5186 5449
2100 4949
8352 9818
2719 9527
2963 9138
4577 4992
7977 9142
1697 5118
5661 8807
...

output:

5087

result:

ok 1 number(s): "5087"

Test #13:

score: 0
Accepted
time: 2613ms
memory: 7108kb

input:

5000
3569 5853
3805 9296
6077 8227
5992 8647
3355 6981
2910 5083
1995 2252
5990 6301
3466 4029
2481 4730
5314 6440
2567 5631
4299 5829
568 9502
6066 9604
2527 4983
4791 8244
5023 7341
2629 3977
2192 2462
2137 3400
1380 7387
2864 7832
2975 7576
2840 2928
5924 6542
1007 1728
933 4876
1169 7206
4836 49...

output:

5104

result:

ok 1 number(s): "5104"

Test #14:

score: 0
Accepted
time: 14ms
memory: 6764kb

input:

5000
871 9565
987 9507
2149 8926
2382 6310
2073 8964
3670 5666
2227 8887
2563 8719
4107 7947
3087 8457
2852 6075
1423 9289
1042 6980
969 9516
98 7452
4069 7966
2038 6482
4364 5319
3057 8472
2412 6295
523 9739
2026 6488
4777 7612
1761 9120
2740 6131
1295 9353
2241 8880
1034 6984
428 7287
376 7313
160...

output:

7501

result:

ok 1 number(s): "7501"

Test #15:

score: 0
Accepted
time: 7ms
memory: 6708kb

input:

4999
3207 8395
3675 8161
4846 5076
2968 6015
1037 9480
4634 5182
548 7225
2984 6007
2316 6341
1164 6917
460 7269
3885 8056
4254 5372
2730 6134
4906 5046
3282 5858
1300 6849
3875 8061
1414 6792
786 7106
1201 9398
4052 5473
1236 6881
3066 5966
182 7408
2875 8561
2229 8884
2135 8931
2397 8800
427 9785
...

output:

7499

result:

ok 1 number(s): "7499"

Test #16:

score: 0
Accepted
time: 0ms
memory: 6632kb

input:

4999
5431 5436
2916 2917
582 587
137 144
6660 6661
4890 4897
5300 5303
66 72
5708 5711
3735 3737
5298 5301
1900 1912
1304 1306
9900 9902
537 541
5019 5020
5334 5338
7279 7283
8186 8190
3660 3665
458 460
4588 4589
9828 9832
7850 7852
7561 7564
8193 8195
1872 1875
3638 3641
6346 6347
2378 2379
4187 41...

output:

8131

result:

ok 1 number(s): "8131"

Test #17:

score: 0
Accepted
time: 0ms
memory: 6700kb

input:

4999
8363 8375
1371 1372
1038 1045
1741 1742
9672 9673
5734 5738
8369 8372
1414 1427
7767 7771
7970 7983
4403 4409
3720 3724
8958 8959
7311 7312
6365 6378
331 338
3975 3982
4356 4357
6195 6206
3009 3010
7591 7602
6554 6558
1195 1202
4417 4418
7990 7993
4900 4914
7921 7927
2504 2508
5043 5047
4324 43...

output:

7066

result:

ok 1 number(s): "7066"

Test #18:

score: 0
Accepted
time: 2ms
memory: 6768kb

input:

4999
5839 5845
6903 6906
3785 3798
5232 5253
1216 1227
378 402
7691 7693
1359 1369
5901 5908
5117 5118
7752 7755
7229 7254
650 674
4571 4584
7617 7660
2197 2208
503 509
4965 4969
2375 2385
2743 2745
757 768
1988 1994
667 673
5053 5062
9796 9818
6843 6867
577 581
4514 4538
2248 2261
3025 3035
672 699...

output:

6366

result:

ok 1 number(s): "6366"

Test #19:

score: 0
Accepted
time: 11ms
memory: 6740kb

input:

4999
1052 1056
1180 1191
606 614
3449 3480
811 827
9191 9233
9559 9578
6572 6587
2932 2933
2245 2293
4081 4088
5994 6034
6534 6565
7417 7418
2123 2160
226 232
9627 9652
9836 9857
1734 1748
1062 1063
3811 3822
5006 5030
9942 9966
692 721
3694 3699
543 567
1379 1396
9691 9736
7961 7962
3752 3755
4124 ...

output:

5622

result:

ok 1 number(s): "5622"

Test #20:

score: 0
Accepted
time: 83ms
memory: 6960kb

input:

4999
441 443
8409 8433
3652 3682
5308 5375
2255 2299
7239 7248
6585 6659
7834 7921
8492 8532
4806 4881
6294 6387
1324 1383
2737 2809
1045 1129
6352 6399
8756 8775
5120 5171
7981 8016
8598 8608
839 883
8506 8518
694 833
4038 4043
2357 2366
2439 2581
5560 5688
7014 7040
9281 9317
2769 2825
7279 7280
7...

output:

5259

result:

ok 1 number(s): "5259"

Test #21:

score: 0
Accepted
time: 228ms
memory: 6852kb

input:

4999
9430 9436
601 695
480 515
9413 9433
3585 3785
9228 9318
3219 3483
5648 5842
8273 8342
3379 3398
1716 1797
6100 6152
1185 1322
4411 4633
4321 4364
2521 2561
4953 5009
5221 5311
378 513
4058 4140
5184 5314
631 632
4509 4536
6977 7020
3309 3443
7676 7740
507 934
8420 8502
238 436
8159 8423
570 654...

output:

5134

result:

ok 1 number(s): "5134"

Test #22:

score: 0
Accepted
time: 351ms
memory: 7112kb

input:

4999
4317 4457
8422 8554
4906 5161
6527 7079
1220 1350
1010 1032
3592 3676
3700 3719
5038 5079
4532 4535
4677 4788
3371 3527
857 987
6826 7186
5958 6044
7846 8542
4805 5561
4191 4390
2669 2682
1594 1937
504 605
6856 7251
1240 1528
5170 5201
481 587
2031 2248
9508 9951
6542 6867
8685 8889
7007 7044
2...

output:

5066

result:

ok 1 number(s): "5066"

Test #23:

score: 0
Accepted
time: 940ms
memory: 7020kb

input:

4999
6643 6946
2015 2127
7853 8773
1592 2602
6495 6880
8086 8933
8599 9434
3350 3932
5285 5348
400 658
5843 5936
5506 5522
5762 6131
1290 1653
6150 6551
479 660
2991 2996
7500 7632
3316 3491
8851 8956
8481 8792
5143 5191
1342 1508
6074 6108
2644 3505
7497 7757
7955 8228
2214 2571
1938 3123
992 1383
...

output:

5059

result:

ok 1 number(s): "5059"

Test #24:

score: 0
Accepted
time: 1425ms
memory: 7212kb

input:

4999
7318 7668
3670 3794
243 2954
56 1573
5805 7851
9 2407
454 1393
725 1779
9709 9871
3481 3522
9129 9475
7811 9385
1017 1681
3065 3462
4135 4655
34 755
974 1071
865 1072
4288 4471
7738 8449
15 242
8161 9263
1613 2188
5321 5847
3330 3924
7839 8239
8158 8516
4142 4315
5039 5077
6081 6592
5677 5862
6...

output:

5056

result:

ok 1 number(s): "5056"

Test #25:

score: 0
Accepted
time: 2018ms
memory: 6996kb

input:

4999
4992 5718
358 2562
4128 4297
246 3376
907 2019
2076 3951
2850 6203
617 4942
192 2300
188 2135
293 3550
3026 4557
2493 6702
3476 7470
3937 6193
3725 3762
813 4969
4810 5944
5398 7553
4357 7793
1809 2988
6862 7467
3835 4012
3271 5647
6768 9968
6028 6634
5914 7535
8012 8594
7361 7524
397 1573
3374...

output:

5070

result:

ok 1 number(s): "5070"

Test #26:

score: 0
Accepted
time: 2503ms
memory: 7012kb

input:

4999
3163 8330
9027 9342
106 4633
7484 8163
6892 9248
1330 2769
4258 8600
800 3843
3355 7035
1899 6283
1440 3789
1364 3473
4916 9317
3603 8620
2184 3368
6190 7077
411 1780
3437 4966
6980 7333
1125 6406
5861 7744
712 9508
1867 3548
1963 8426
7811 9570
5396 6271
7195 9829
5219 6486
2337 4288
3364 5668...

output:

5086

result:

ok 1 number(s): "5086"

Test #27:

score: 0
Accepted
time: 2671ms
memory: 7096kb

input:

4999
845 1599
782 3268
1007 1460
6298 8042
6934 9545
2486 5021
5151 6493
1631 2090
1345 2253
1539 2735
8856 9538
1822 2957
3777 8337
881 3952
7171 7325
5346 7124
4341 8176
2830 8935
4010 5545
2746 8196
5410 6949
4496 5499
8194 9133
3221 7828
2213 4329
125 6246
8259 9008
1319 5858
4767 9114
3675 5041...

output:

5096

result:

ok 1 number(s): "5096"

Test #28:

score: 0
Accepted
time: 411ms
memory: 6968kb

input:

5000
5185 5200
9772 9776
818 854
2803 2815
9028 9075
8856 8893
6548 6550
4312 4423
5811 5822
3900 3933
1402 1546
2429 2456
7808 7823
6090 6155
3087 3089
9015 9110
1633 1755
9497 9649
2280 2417
151 205
7052 7106
6438 6447
6835 6867
6852 6898
2540 2556
57 88
7609 7622
6781 6798
7771 7840
5333 5343
758...

output:

5225

result:

ok 1 number(s): "5225"

Test #29:

score: 0
Accepted
time: 51ms
memory: 6796kb

input:

4999
5156 5247
3007 3065
4110 4138
1814 1873
132 163
4521 4554
3466 3494
9630 9671
3914 3942
969 992
3365 3423
7136 7149
6873 6930
6632 6683
5655 5683
2770 2796
4909 4970
5830 5852
8341 8476
9036 9050
993 1278
8339 8366
22 148
3554 3649
2484 2487
1218 1226
9914 9930
9427 9431
6305 6320
1841 1890
912...

output:

5224

result:

ok 1 number(s): "5224"

Test #30:

score: 0
Accepted
time: 2911ms
memory: 7148kb

input:

5000
1708 9430
234 2683
2108 4320
841 2215
2421 7664
8977 9327
4221 8868
723 7208
248 1554
4913 8512
3388 4471
6180 7609
1325 5327
3476 8584
2105 9064
4369 5765
5088 5451
7147 9405
4204 7540
6394 7230
7138 9107
1623 8360
5166 6089
972 5847
1915 5345
6953 8309
552 1356
4718 9296
8414 9050
4645 8510
5...

output:

5097

result:

ok 1 number(s): "5097"

Test #31:

score: -100
Time Limit Exceeded

input:

5000
3714 3967
3165 6901
1796 7494
775 7440
6010 8297
4737 6454
2970 6630
1429 5812
3580 5112
3178 5868
628 7138
1525 8276
1583 4018
1341 4213
76 4851
6670 9978
7229 8292
377 2595
9362 9676
4205 6575
3942 7342
2940 3148
4892 5863
4389 8236
5176 5533
43 4387
2992 7261
5481 5751
5130 6273
6265 8123
62...

output:


result: