QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#413097 | #1768. 廊桥分配 | x-camp | 90 | 886ms | 11104kb | C++17 | 2.8kb | 2024-05-17 05:09:20 | 2024-05-17 05:09:20 |
Judging History
answer
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <fstream>
#include <cstring>
using namespace std;
#define ar first
#define de second
int N, m1, m2;
#define MX 100005
vector<pair<int,int>> s1, s2;
int parked[MX];
vector<pair<pair<int,int>,pair<int,int>>> t1, t2;
int ans;
int schedule (vector<pair<int,int>> &s, int sz, vector<pair<pair<int,int>,pair<int,int>>> & t) {
if (t.empty()) {
for (int i=0; i<s.size(); i++) {
auto p = s[i];
t.push_back({p,{1,i}});
t.push_back({{p.second,p.first},{2,i}});
}
sort(t.begin(),t.end());
}
vector<int> parkedAir;
vector<bool> in( (int) s.size());
int cur = 0;
int endtime = 0;
int parked = 0;
for (int i=0; i<t.size();i++) {
auto &e = t[i];
if (e.second.first == 1) { // arrival time
if (cur < sz ) {
cur++;
parked++;
parkedAir.push_back(cur);
in[e.second.second] = true; //parked in bridge
}
}
else { // departure time
if (in[e.second.second]) cur --;
}
}
return parked;
}
int res[MX];
void quadSearch(int start, int end) {
if (start ==0)
res[start] = schedule(s1, start, t1) + schedule(s2,N-start , t2);
if (end ==N)
res[end] = schedule(s1, end, t1) + schedule(s2,N-end , t2);
if (end - start <5) {
for (int i = max(0,start - 350); i<=min(N, end+350); i++) {
res[i] = schedule(s1, i, t1) + schedule(s2, N-i, t2);
ans = max(ans, res[i]);
}
} else {
int left = start + (end -start)/4, right = start + (end-start)*3/4;
int mid = (start + end) /2;
int q1 = schedule(s1, left, t1) + schedule(s2,N-left , t2);
int q2 = schedule(s1, mid, t1) + schedule(s2,N-mid , t2);
int q3 = schedule(s1, right, t1) + schedule(s2,N-right , t2);
if (start > q2) quadSearch(start, mid);
else if (end > q2) quadSearch(mid, end);
else if (q2 >= q1 && q2 >= q3) quadSearch(left, right);
else if (q1 > q2 && q2 >= q3) quadSearch(start, left);
else quadSearch(right, end);
}
return;
}
int main() {
cin >> N >> m1 >> m2;
for (int i=0; i<m1; i++) {
int a,b;
cin >> a >> b;
s1.push_back({a,b});
}
for (int i=0; i<m2; i++) {
int a,b;
cin >> a >> b;
s2.push_back({a,b});
}
int best = 0;
/*for (int i=0; i<=N; i++) {
best = max(best, schedule(s1, i,t1) + schedule(s2, N-i,t2));
}*/
quadSearch(0, N);
/*
cout << best << " " << ans << endl;
for (int i=0; i<=N; i++)
cout << res[i] << " ";
cout << endl; */
cout << ans;
return 0;
}
详细
Test #1:
score: 5
Accepted
time: 1ms
memory: 3512kb
input:
2 5 10 36 275 131 223 222 308 40 60 50 70 61 80 71 90 81 100 167 240 101 120 166 220 46 194 130 150 186 243 153 170
output:
7
result:
ok single line: '7'
Test #2:
score: 5
Accepted
time: 1ms
memory: 3560kb
input:
1 10 10 54 407 300 409 251 303 87 265 50 169 120 140 142 160 161 180 181 200 147 275 33 312 240 260 102 368 132 283 64 310 320 340 341 360 79 272 92 289 9 249
output:
3
result:
ok single line: '3'
Test #3:
score: 5
Accepted
time: 0ms
memory: 3568kb
input:
10 99 1 155 1946 40 60 365 463 80 100 103 120 122 140 142 160 161 180 181 200 1567 2008 220 240 46 809 260 280 281 300 301 320 321 340 341 360 1317 1326 322 941 58 1191 420 440 441 460 183 1910 480 500 1022 1536 878 1367 987 1356 560 580 581 600 1544 2056 620 640 601 1550 660 680 683 700 702 720 721...
output:
83
result:
ok single line: '83'
Test #4:
score: 5
Accepted
time: 1ms
memory: 3396kb
input:
90 50 50 10 1020 20 1030 1398 1701 40 1050 50 1060 1150 2064 70 1080 80 1090 406 883 100 1110 110 1120 976 1051 130 1140 140 1151 150 1160 160 1170 170 1180 180 1190 1304 1714 200 1210 210 1220 857 1911 230 1240 240 1250 250 1260 260 1270 270 1280 280 1290 290 1300 253 2058 310 1320 320 1330 330 134...
output:
100
result:
ok single line: '100'
Test #5:
score: 5
Accepted
time: 6ms
memory: 3668kb
input:
500 100 2500 10 30 17270 54239 20587 38706 41984 50712 38874 51450 29278 39413 27866 30516 80 100 1019 4953 10516 24884 22450 43548 120 140 3481 52726 42611 50244 150 170 22555 29759 171 190 180 200 46368 49203 905 43468 210 230 220 240 231 250 241 260 251 270 261 280 271 290 281 300 20880 50387 301...
output:
2218
result:
ok single line: '2218'
Test #6:
score: 5
Accepted
time: 17ms
memory: 3652kb
input:
2000 2500 2500 10 50020 20 50030 30 50040 40 50050 50 50060 60 50070 70 50080 80 50090 90 50100 100 50110 110 50120 120 50130 130 50140 140 50150 150 50160 160 50170 170 50180 180 50190 190 50200 200 50210 210 50220 220 50230 230 50240 240 50250 250 50260 270 35539 271 50280 280 50290 886 64769 300 ...
output:
2084
result:
ok single line: '2084'
Test #7:
score: 5
Accepted
time: 25ms
memory: 3960kb
input:
2000 2500 2500 9065348 22025433 21761416 57104176 47512139 65864276 38073363 54309128 3361316 52318297 37212767 62708135 46815160 80343130 8340912 33061898 28313363 76481521 77661079 87322090 20171513 99089799 64298534 72795270 12768040 29120020 3671034 13911707 1070586 92178043 25346307 92197016 71...
output:
4348
result:
ok single line: '4348'
Test #8:
score: 5
Accepted
time: 12ms
memory: 3652kb
input:
400 4000 1000 20 40 21990 96255 60 80 82 100 103 120 121 140 141 160 17378 18142 180 200 201 220 223 240 241 260 261 280 281 300 301 320 321 340 341 360 361 380 381 400 401 420 421 440 442 460 8012 80919 480 500 501 520 521 540 542 560 562 580 581 600 601 620 621 640 48998 51608 660 680 1220 34859 7...
output:
4717
result:
ok single line: '4717'
Test #9:
score: 5
Accepted
time: 24ms
memory: 3948kb
input:
100000 2500 2500 4327949 93174054 27756096 93487018 54718595 83760723 23570765 89475375 61923176 80628357 19270586 51315517 66531506 68484116 39628263 78932267 16721909 48858824 9814614 20767667 51116028 58318647 3591452 50525832 28049059 38849006 35224606 56268814 20667491 38685668 58912622 6619444...
output:
5000
result:
ok single line: '5000'
Test #10:
score: 5
Accepted
time: 586ms
memory: 8552kb
input:
70000 50000 50000 338731 1909627 341955 1871866 30 1000040 168753 815991 50 1000060 60 1000070 70 1000080 1201255 1996909 88733 588226 100 1000110 960271 1925720 457332 769685 130 1000140 140 1000150 974625 1922736 160 1000170 1122514 1289366 987241 1787245 190 1000200 200 1000210 395149 1973184 220...
output:
94831
result:
ok single line: '94831'
Test #11:
score: 5
Accepted
time: 886ms
memory: 11104kb
input:
20000 10000 90000 715805 1008115 20 40 30 50 957353 1618719 612791 704464 1205978 1332921 70 90 80 100 495171 1195450 102 120 110 130 121 140 392946 1347254 1750364 1872927 432686 1262110 160 180 170 190 1031792 1182304 688141 1040298 275788 2019895 210 230 1354503 1413439 231 250 392916 1675523 251...
output:
88989
result:
ok single line: '88989'
Test #12:
score: 5
Accepted
time: 549ms
memory: 8616kb
input:
9000 50000 50000 20 40 42 60 61 80 82 100 102 120 121 140 1286466 1689882 143089 1200200 452857 1312030 200 220 221 240 828765 1252736 260 280 281 300 358027 1095227 320 340 1364952 1486461 360 380 381 400 620378 1087231 788147 1726144 440 460 461 480 481 500 646838 886367 623660 1677846 540 560 561...
output:
98389
result:
ok single line: '98389'
Test #13:
score: 5
Accepted
time: 836ms
memory: 8564kb
input:
40000 50000 50000 37165687 41982847 51657178 70030973 50503218 74872927 14692443 62560081 5749493 98433861 15605226 63964360 36754697 67924829 7670633 35105399 47810908 62007669 13010859 85884618 19866405 33676122 52224408 99584225 44549005 75168299 11891626 78136081 36930868 72843487 32349537 50957...
output:
86837
result:
ok single line: '86837'
Test #14:
score: 5
Accepted
time: 369ms
memory: 9324kb
input:
9000 1 99999 20 40 41 60 47031 1918095 80 100 101 120 121 140 141 160 161 180 182 200 202 220 221 240 241 260 261 280 281 300 301 320 324 340 342 360 1029588 1970602 380 400 979880 1944518 420 440 441 460 461 480 113860 2018256 500 520 522 540 541 560 562 580 581 600 602 620 621 640 643 660 662 680 ...
output:
97015
result:
ok single line: '97015'
Test #15:
score: 5
Accepted
time: 425ms
memory: 8604kb
input:
100000 50000 50000 20 40 41 60 62 80 81 100 101 120 121 140 141 160 161 180 181 200 203 220 222 240 241 260 261 280 281 300 301 320 321 340 341 360 361 380 382 400 401 420 422 440 441 460 462 480 481 500 501 520 521 540 541 560 562 580 581 600 601 620 622 640 641 660 661 680 681 700 701 720 722 740 ...
output:
100000
result:
ok single line: '100000'
Test #16:
score: 5
Accepted
time: 47ms
memory: 8604kb
input:
3 49999 50001 10 30 20 40 31 50 41 60 52 70 62 80 71 90 81 100 91 110 102 120 111 130 122 140 131 150 141 160 152 170 163 180 172 190 181 200 193 210 201 220 211 230 222 240 233 250 242 260 252 270 263 280 272 290 284 300 291 310 301 320 312 330 321 340 332 350 341 360 351 370 362 380 371 390 381 40...
output:
75001
result:
ok single line: '75001'
Test #17:
score: 5
Accepted
time: 827ms
memory: 10804kb
input:
40000 10000 90000 7631955 52448118 27161731 71724713 45581406 77400547 19020113 32734525 2958268 74954149 24732528 97536850 58565498 86669911 27438963 62052162 50134850 79386813 12537972 68479012 91819797 97229839 27734336 33880745 25683966 65143615 7500403 56543990 47046483 59804352 19675750 368273...
output:
86752
result:
ok single line: '86752'
Test #18:
score: 0
Wrong Answer
time: 422ms
memory: 8604kb
input:
80000 50000 50000 738789 2085439 20 1000030 30 1000040 40 1000050 50 1000060 60 1000070 70 1000080 80 1000090 90 1000100 100 1000110 110 1000120 120 1000130 130 1000140 140 1000150 150 1000160 160 1000170 170 1000180 180 1000190 190 1000200 200 1000210 536631 1650744 220 1000230 230 1000240 240 1000...
output:
84944
result:
wrong answer 1st lines differ - expected: '84960', found: '84944'
Test #19:
score: 0
Wrong Answer
time: 821ms
memory: 8224kb
input:
40000 40000 60000 29738074 40339280 47002070 83738606 56332058 64745363 28717614 69964829 35755935 71745732 57705629 82941476 47323995 63449480 14553703 95709625 41504545 55416367 33653314 65419950 10830484 90059582 66837890 72584380 37094318 52941806 60886249 78582452 2575529 20625468 5821359 38004...
output:
86751
result:
wrong answer 1st lines differ - expected: '86772', found: '86751'
Test #20:
score: 5
Accepted
time: 817ms
memory: 8528kb
input:
20000 50000 50000 20 40 1648331 1974235 129539 1828959 969807 1463848 100 120 121 140 141 160 161 180 1242243 2031806 200 220 667578 2056946 1790539 1862004 260 280 503611 1272912 19427 1817250 452707 1377029 462944 755274 360 380 381 400 67498 683223 420 440 330575 400049 460 480 481 500 1331986 18...
output:
91239
result:
ok single line: '91239'