QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#413093#1768. 廊桥分配x-camp55 147ms11220kbC++172.8kb2024-05-17 05:05:092024-05-17 05:05:09

Judging History

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

  • [2024-05-17 05:05:09]
  • 评测
  • 测评结果:55
  • 用时:147ms
  • 内存:11220kb
  • [2024-05-17 05:05:09]
  • 提交

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 - 20); i<=min(N, end+20); 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: 0ms
memory: 3652kb

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

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: 1ms
memory: 3508kb

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: 3436kb

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

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: 0
Wrong Answer
time: 2ms
memory: 3700kb

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:

2083

result:

wrong answer 1st lines differ - expected: '2084', found: '2083'

Test #7:

score: 5
Accepted
time: 6ms
memory: 3644kb

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: 2ms
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: 6ms
memory: 3604kb

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: 0
Wrong Answer
time: 103ms
memory: 8488kb

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:

94830

result:

wrong answer 1st lines differ - expected: '94831', found: '94830'

Test #11:

score: 0
Wrong Answer
time: 135ms
memory: 9708kb

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:

88971

result:

wrong answer 1st lines differ - expected: '88989', found: '88971'

Test #12:

score: 0
Wrong Answer
time: 91ms
memory: 8504kb

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:

98278

result:

wrong answer 1st lines differ - expected: '98389', found: '98278'

Test #13:

score: 0
Wrong Answer
time: 147ms
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:

86822

result:

wrong answer 1st lines differ - expected: '86837', found: '86822'

Test #14:

score: 5
Accepted
time: 93ms
memory: 10044kb

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: 91ms
memory: 8696kb

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: 38ms
memory: 8492kb

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: 0
Wrong Answer
time: 133ms
memory: 11220kb

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:

86745

result:

wrong answer 1st lines differ - expected: '86752', found: '86745'

Test #18:

score: 0
Wrong Answer
time: 91ms
memory: 8496kb

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:

84853

result:

wrong answer 1st lines differ - expected: '84960', found: '84853'

Test #19:

score: 0
Wrong Answer
time: 137ms
memory: 8340kb

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:

86689

result:

wrong answer 1st lines differ - expected: '86772', found: '86689'

Test #20:

score: 0
Wrong Answer
time: 121ms
memory: 8560kb

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:

91235

result:

wrong answer 1st lines differ - expected: '91239', found: '91235'