QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#482326#4065. Airport CoffeeEasonLiangAC ✓483ms89028kbC++143.4kb2024-07-17 18:56:462024-07-17 18:56:47

Judging History

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

  • [2024-07-17 18:56:47]
  • 评测
  • 测评结果:AC
  • 用时:483ms
  • 内存:89028kb
  • [2024-07-17 18:56:46]
  • 提交

answer

#include <bits/stdc++.h>
#define FileIO_(file) \
    freopen (file ".in", "r", stdin); \
    freopen (file ".out", "w", stdout);

using namespace std;

template<typename Tp>
inline void chmin (Tp &x, const Tp &y) { if (y < x) x = y; }
template<typename Tp>
inline void chmax (Tp &x, const Tp &y) { if (x < y) x = y; }

typedef double dbl;
typedef long long ll;
typedef long double ldb;

void init () {}

const int maxn = 5e5 + 20;
int a, b, t, r, n, pre[maxn];
ll l, p[maxn];

vector<int> ans;

#define ls (u << 1)
#define rs (ls | 1)
#define mid ((l + r) >> 1)

struct Line {
    ldb k, b;
    Line (ldb k, ldb b):
        k (k), b (b) {}
    ldb calc (ll pos) {
        return k * p[pos] + b;
    }
};

vector<Line> vlin;
vector<int> vtyp;

int newLine (ldb k, ldb b, int typ) {
    int id = vlin.size ();
    vlin.emplace_back (k, b);
    vtyp.emplace_back (typ);
    return id;
}

int tr[4 * maxn];

void modify (int u, int l, int r, int id) {
    if (vlin[id].calc (mid) < vlin[tr[u]].calc (mid)) swap (tr[u], id);
    if (vlin[id].calc (l) < vlin[tr[u]].calc (l)) modify (ls, l, mid, id);
    if (vlin[id].calc (r) < vlin[tr[u]].calc (r)) modify (rs, mid + 1, r, id);
}

void modify (int u, int l, int r, int x, int y, int id) {
    if (y < l || r < x) return;
    if (x <= l && r <= y) return modify (u, l, r, id);
    modify (ls, l, mid, x, y, id);
    modify (rs, mid + 1, r, x, y, id);
}

int query (int u, int l, int r, int p) {
    if (l == r) return tr[u];
    int oth = p <= mid ?
        query (ls, l, mid, p) :
        query (rs, mid + 1, r, p);
    return vlin[tr[u]].calc (p) <
        vlin[oth].calc (p) ? tr[u] : oth;
}

#undef ls
#undef rs
#undef mid

void solve () {
    scanf ("%lld%d%d%d%d%d", &l, &a, &b, &t, &r, &n);
    ll adis = a * t; ll bdis = adis + b * r;
    for (int i = 1; i <= n; ++i)
        scanf ("%lld", &p[i]);
    p[n + 1] = l;
    sort (p + 1, p + n + 1);
    vlin.emplace_back ((ldb) 1 / a, 0);
    vtyp.emplace_back (0);
    for (int i = 1; i <= n; ++i) {
        int id = query (1, 1, n + 1, i); pre[i] = vtyp[id];
        ldb dpv = vlin[id].calc (i);
        int ap = upper_bound (p + i + 1, p + n + 2, p[i] + adis) - p - 1;
        int bp = upper_bound (p + i + 1, p + n + 2, p[i] + bdis) - p - 1;
        modify (1, 1, n + 1, i + 1, ap, newLine ((ldb) 1 / a, dpv - (ldb) p[i] / a, i));
        modify (1, 1, n + 1, ap + 1, bp, newLine ((ldb) 1 / b, dpv + t - (ldb) (p[i] + adis) / b, i));
        modify (1, 1, n + 1, bp + 1, n + 1, newLine ((ldb) 1 / a, dpv + t + r - (ldb) (p[i] + bdis) / a, i));
    }
    int u = n + 1;
    pre[n + 1] = vtyp[query (1, 1, n + 1, n + 1)];
    while ((u = pre[u])) ans.emplace_back (u - 1);
    reverse (ans.begin (), ans.end ());
    printf ("%d\n", (int) ans.size ());
    for (int p : ans) printf ("%d ", p);
}

int main () {
    // #ifndef LSY
    // FileIO_("");
    // #endif
    int t = 1; init ();
    // scanf ("%d", &t);
    while (t--) solve ();
    return 0;
}

// #ifdef LSY
// bool ed, debug = [] () {
//     static bool st; int memtyp = 0; dbl memsiz = &st - &ed;
//     static const string memstr[] = {"B", "KB", "MB", "GB"};
//     while (memsiz >= 1024.) { ++memtyp; memsiz /= 1024.; }
//     cerr << "Memory: " << memsiz << memstr[memtyp] << endl;
//     return atexit ([] () { cerr << "Time: " << 1000. *
// 		clock () / CLOCKS_PER_SEC << "ms" << endl; });
// } ();
// #endif

详细

Test #1:

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

input:

100000 100 138 60 300
5
5000 20000 50000 55000 75000

output:

2
0 2 

result:

ok 

Test #2:

score: 0
Accepted
time: 1ms
memory: 8008kb

input:

100000 78 86 9 560
4
13505 69705 87448 92090

output:

2
0 1 

result:

ok 

Test #3:

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

input:

1 1 2 0 1
0


output:

0

result:

ok 

Test #4:

score: 0
Accepted
time: 438ms
memory: 87420kb

input:

100000000000 199 200 300 1200
495002
99969970299 99970265000 99970265001 99970265002 99970265003 99970265004 99970265005 99970265006 99970265007 99970265008 99970265009 99970265010 99970265011 99970265012 99970265013 99970265014 99970265015 99970265016 99970265017 99970265018 99970265019 99970265020...

output:

101
0 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 55000 60000 65000 70000 75000 80000 85000 90000 95000 100000 105000 110000 115000 120000 125000 130000 135000 140000 145000 150000 155000 160000 165000 170000 175000 180000 185000 190000 195000 200000 205000 210000 215000 220000 225000...

result:

ok 

Test #5:

score: 0
Accepted
time: 431ms
memory: 86404kb

input:

100000000000 199 200 300 1200
490002
99984955299 99985245000 99985245001 99985245002 99985245003 99985245004 99985245005 99985245006 99985245007 99985245008 99985245009 99985245010 99985245011 99985245012 99985245013 99985245014 99985245015 99985245016 99985245017 99985245018 99985245019 99985245020...

output:

51
0 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000 110000 120000 130000 140000 150000 160000 170000 180000 190000 200000 210000 220000 230000 240000 250000 260000 270000 280000 290000 300000 310000 320000 330000 340000 350000 360000 370000 380000 390000 400000 410000 420000 430000 440...

result:

ok 

Test #6:

score: 0
Accepted
time: 202ms
memory: 50524kb

input:

100000000000 199 200 300 1200
300000
10090239999 10090539699 10090839399 10091139099 10091438799 10091738499 10092038199 10092337899 10092637599 10092937299 10093236999 10093536699 10093836399 10094136099 10094435799 10094735499 10095035199 10095334899 10095634599 10095934299 10096233999 10096533699...

output:

300000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100...

result:

ok 

Test #7:

score: 0
Accepted
time: 432ms
memory: 87336kb

input:

100000000000 199 200 300 1200
496002
14003386 146194493 185180213 214013033 264026131 498334272 615931118 969855298 1031994435 1043227054 1078520208 1108164943 1270463472 1663185749 1717442087 1727405671 1936982608 1941780263 2010554231 2237260053 2510186168 2594900453 2603436937 2615340283 27538886...

output:

1100
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok 

Test #8:

score: 0
Accepted
time: 435ms
memory: 87752kb

input:

100000000000 199 200 300 1200
491002
430609 116821677 168287615 233365248 554808755 645556365 788934350 812755860 814729432 903514871 973212675 1037478308 1100751728 1197751334 1400472175 1684326395 1833452748 1864443408 1974354609 2076942712 2229949841 2252240410 2258953353 2330738757 2363489827 24...

output:

1051
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok 

Test #9:

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

input:

80 1 2 20 10
3
0 40 41

output:

2
0 1 

result:

ok 

Test #10:

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

input:

80 1 2 20 10
3
0 39 40

output:

2
0 2 

result:

ok 

Test #11:

score: 0
Accepted
time: 433ms
memory: 86272kb

input:

100000000000 1 200 300 1200
500000
0 240299 240300 240301 480598 480599 480600 480601 480602 720897 720898 720899 720900 720901 720902 720903 961196 961197 961198 961199 961200 961201 961202 961203 961204 1201495 1201496 1201497 1201498 1201499 1201500 1201501 1201502 1201503 1201504 1201505 1441794...

output:

708
0 1 5 10 18 28 40 52 68 86 106 128 150 174 202 232 264 298 334 372 412 454 498 544 591 639 691 744 800 858 918 980 1044 1110 1178 1248 1320 1394 1470 1548 1628 1710 1794 1880 1968 2058 2148 2241 2337 2434 2534 2634 2737 2843 2949 3059 3171 3285 3401 3519 3639 3761 3885 4011 4139 4269 4401 4535 4...

result:

ok 

Test #12:

score: 0
Accepted
time: 483ms
memory: 87892kb

input:

100000000000 35 200 300 1200
500000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 9...

output:

3
0 249507 499999 

result:

ok 

Test #13:

score: 0
Accepted
time: 449ms
memory: 89028kb

input:

100000000000 35 200 300 1200
500000
99999500001 99999500002 99999500003 99999500004 99999500005 99999500006 99999500007 99999500008 99999500009 99999500010 99999500011 99999500012 99999500013 99999500014 99999500015 99999500016 99999500017 99999500018 99999500019 99999500020 99999500021 99999500022 ...

output:

3
0 249499 499999 

result:

ok 

Test #14:

score: 0
Accepted
time: 324ms
memory: 86760kb

input:

100000000000 1 199 300 999
500000
0 145701 415401 713275 899916 1092845 1389469 1537546 1681338 1927558 2203262 2474072 2720032 2982209 3222175 3497632 3792674 4010448 4271276 4472343 4701013 4826977 5009635 5266942 5382407 5566354 5780551 6052740 6263926 6491746 6724826 6958130 7221259 7517786 7677...

output:

500000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100...

result:

ok 

Test #15:

score: 0
Accepted
time: 327ms
memory: 88100kb

input:

100000000000 150 200 300 1200
500000
124854 159679 248908 277292 338655 351941 383398 559870 569701 626657 821187 939428 991034 1152701 1264627 1453639 1705278 1780764 1851281 2261046 2398891 2592788 2703688 2719112 2965060 3003596 3026157 3231433 3237988 3411390 3712537 3738048 3765705 3990984 4227...

output:

311126
0 5 9 11 13 15 16 18 19 20 22 24 27 29 30 33 35 36 37 38 40 41 44 46 47 48 50 53 54 55 56 57 58 59 61 62 64 65 69 70 71 74 75 77 78 81 84 85 86 87 88 89 91 92 93 95 99 100 101 102 104 105 108 113 117 118 119 121 122 123 124 126 127 128 133 134 136 137 138 140 141 142 144 147 149 150 151 154 1...

result:

ok 

Test #16:

score: 0
Accepted
time: 37ms
memory: 18084kb

input:

10000000 53 66 233 704
51659
30 572 801 916 1188 1404 1506 1976 2044 2049 2093 2147 3417 3595 3850 4520 4604 4702 4783 4827 4940 5209 5370 5372 5378 5527 5554 5680 5684 6292 6869 6970 7030 7070 7104 7145 7265 7421 7676 7779 8090 8314 8341 8383 8446 8666 9043 9340 9759 9791 10271 10718 10726 10752 10...

output:

181
0 279 572 879 1193 1483 1788 2111 2417 2702 3022 3336 3629 3927 4233 4517 4519 4831 5149 5440 5737 6034 6318 6602 6924 7250 7581 7892 8195 8509 8848 9144 9465 9759 10066 10409 10718 11010 11345 11645 11970 12273 12274 12588 12896 13211 13515 13802 14094 14396 14686 15011 15282 15580 15889 16211 ...

result:

ok 

Test #17:

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

input:

1000000 90 154 208 910
25253
12 20 76 98 101 138 235 258 303 359 411 457 458 511 526 546 578 637 644 687 721 783 808 836 879 887 972 1016 1092 1122 1230 1249 1258 1282 1290 1303 1363 1370 1386 1466 1476 1550 1566 1605 1688 1870 2006 2152 2177 2226 2228 2275 2322 2424 2429 2439 2441 2448 2465 2488 24...

output:

7
0 3782 7765 11729 15814 19162 23205 

result:

ok 

Test #18:

score: 0
Accepted
time: 1ms
memory: 8184kb

input:

1000000 192 197 205 20
610
1486 1613 1698 4376 5132 6673 9087 21073 21234 22185 22490 23678 24091 24491 35627 37345 39479 40506 41706 42350 42761 43311 46952 48018 51188 52388 52877 55137 55531 60115 61166 63348 66713 68138 68305 68474 69503 72361 73119 74448 74805 75234 77969 78678 81828 84222 8549...

output:

24
0 22 51 81 109 140 168 194 226 253 275 300 332 362 394 427 450 451 470 495 520 554 583 609 

result:

ok 

Test #19:

score: 0
Accepted
time: 1ms
memory: 8012kb

input:

100000 194 199 166 745
1
99673

output:

0

result:

ok 

Test #20:

score: 0
Accepted
time: 1ms
memory: 7992kb

input:

100000 98 157 20 985
10
4690 18636 26423 32876 36825 39390 60465 80049 83060 91202

output:

1
0 

result:

ok 

Test #21:

score: 0
Accepted
time: 1ms
memory: 5972kb

input:

100000 23 134 78 769
0


output:

0

result:

ok 

Test #22:

score: 0
Accepted
time: 1ms
memory: 8144kb

input:

1000000 180 199 64 885
756
19 1033 2311 7610 8034 8363 10151 11006 12525 12632 13292 15650 16351 17618 18252 20570 24273 25027 27464 27997 28048 28399 29414 31050 32357 33342 36136 37556 44026 44603 45487 45846 46582 46747 47319 49268 51074 52319 53837 55556 55935 57801 58957 59854 60740 62761 62922...

output:

6
0 133 254 408 561 709 

result:

ok 

Test #23:

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

input:

1000000 70 73 28 811
622
701 4501 8446 9014 11467 11513 11632 17231 19189 23168 24874 25070 30004 30367 30548 34271 40069 42652 43398 43400 44890 47393 51591 57593 58025 58762 60515 60606 60803 63182 63609 64626 65612 66785 71699 71895 72621 73147 75073 76634 77541 78439 79000 81554 82078 85594 8676...

output:

17
0 23 60 102 136 176 212 263 298 332 370 414 441 481 510 546 584 

result:

ok 

Test #24:

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

input:

1000000 33 116 76 526
175
10608 17379 18587 25704 27183 39810 45774 53206 53487 55840 64746 66050 68494 71897 75298 86871 89908 90353 95308 102099 105242 110196 111949 119969 123315 124015 126042 126819 127652 132844 133882 134698 138375 146709 157615 182197 184650 189638 192376 192947 197689 199796...

output:

17
0 13 31 40 55 64 79 88 93 101 107 114 122 133 142 155 165 

result:

ok