QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#487055#8257. Marathon Race 2bashkort7 0ms3832kbC++204.2kb2024-07-22 15:39:312024-07-22 15:39:31

Judging History

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

  • [2024-07-22 15:39:31]
  • 评测
  • 测评结果:7
  • 用时:0ms
  • 内存:3832kb
  • [2024-07-22 15:39:31]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, L;
    cin >> n >> L;

    vector<int> x(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    sort(x.begin(), x.end());

    int q;
    cin >> q;
    vector<int> from(q), to(q), limit(q);
    vector<ll> answer(q, 3e18);
    for (int i = 0; i < q; ++i) {
        cin >> from[i] >> to[i] >> limit[i];
    }

    for (int _ = 0; _ < 2; ++_) {
        vector<ll> pref(n + 1);
        for (int i = 0; i < n; ++i) {
            pref[i + 1] = pref[i] + x[i];
        }
        auto rangeSum = [&](int l, int r) {
            return pref[r] - pref[l];
        };
        auto query = [&](int fin, int mid, int u, int c) -> ll {
            ll now = 0;
//            if (mid == 0 && c == 1) {
//                cout << "here!" << endl;
//            }
            int nx = (mid + 1 < n && x[mid + 1] <= fin ? x[mid + 1] : fin);
            int cord = (c > 0 && u + c - 1 < n ? x[u + c - 1] : fin);
            if (mid >= 0) {
                now += 1LL * fin * (mid + 1) - rangeSum(0, mid + 1);
                now += 1LL * (mid + 1) * 2 * ((fin - nx) + (max(fin, x.back()) - fin) + (cord - fin));
            }
            if (u + c < n) {
                int cnt = (n - u - c);
                now += rangeSum(n - cnt, n) - 1LL * cnt * fin;
                now += 1LL * ((fin - nx) + (cord - fin)) * 2 * cnt;
            }
            if (mid + 1 < u) {
                int cnt = (u - mid - 1);
                now += 1LL * cnt * fin - rangeSum(mid + 1, u);
                now += 1LL * cnt * (cord - fin) * 2;
            }
            if (c > 0) {
                now += rangeSum(u, u + c) - 1LL * c * fin;
            }
            now += fin - x[0] + (u < n ? 2 * (x.back() - fin) : 0) + 2 * (fin - nx) + 2 * (cord - fin);
            return now;
        };
        for (int i = 0; i < q; ++i) {
            int up = upper_bound(x.begin(), x.end(), to[i]) - x.begin();
            int hi = up - 1, lo = -1;
            ll now = 3e18;
            for (int k = lo; k <= hi; ++k) {
                for (int c = 0; c + up <= n; ++c) {
                    now = min(now, query(to[i], k, up, c));
                }
            }
            now += abs(x[0] - from[i]);
//            cout << now << endl;
            auto stupid = [&]() {
                vector<int> p(n);
                iota(p.begin(), p.end(), 0);
                do {
                    int c = from[i], cnt = 1, ans = 0;
                    for (int j = 0; j < n; ++j) {
                        ans += abs(c - x[p[j]]) * cnt;
                        c = x[p[j]];
                        cnt += 1;
                    }
                    ans += abs(c - to[i]) * cnt;
                    if (ans + n <= 187) {
                        cout << ans << endl;
                        for (int r : p) {
                            cout << r << " ";
                        }
                        cout << endl;
                    }
                    answer[i] = min(answer[i], ll(ans));
                } while (next_permutation(p.begin(), p.end()));
            };
//            stupid();
            if (0) {
//                while (lo < hi) {
//                    int mid = lo + hi >> 1;
//                    auto u = query(to[i], mid, up);
//                    auto v = query(to[i], mid + 1, up);
//                    now = min({now, u, v});
//                    if (u < v) {
//                        hi = mid;
//                    } else {
//                        lo = mid + 1;
//                    }
//                }
//                now = min(now, query(to[i], lo, up));
            }
//            cout << "now: " << now << endl;
            answer[i] = min(answer[i], now);
        }
        for (int &t : x) {
            t = L - t;
        }
        for (int i = 0; i < q; ++i) {
            from[i] = L - from[i];
            to[i] = L - to[i];
        }
        reverse(x.begin(), x.end());
    }

    for (int i = 0; i < q; ++i) {
//        cout << answer[i] + n << endl;
        cout << (answer[i] + n <= limit[i] ? "Yes\n" : "No\n");
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 7
Accepted

Test #1:

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

input:

1 500000
166666
10
0 0 500000
0 0 499999
0 0 499998
0 0 499997
0 0 499996
0 0 5
0 0 4
0 0 3
0 0 2
0 0 1

output:

Yes
Yes
No
No
No
No
No
No
No
No

result:

ok 10 token(s): yes count is 2, no count is 8

Test #2:

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

input:

1 500000
0
10
0 0 500000
0 0 499999
0 0 499998
0 0 499997
0 0 499996
0 0 5
0 0 4
0 0 3
0 0 2
0 0 1

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 10, no count is 0

Test #3:

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

input:

2 1
0 1
10
0 0 1
0 0 2
0 0 3
0 0 4
0 0 5
0 0 6
0 0 7
0 0 8
0 0 9
0 0 10

output:

No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 6, no count is 4

Test #4:

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

input:

3 1
0 0 1
10
0 0 1
0 0 2
0 0 3
0 0 4
0 0 5
0 0 6
0 0 7
0 0 8
0 0 9
0 0 10

output:

No
No
No
No
No
Yes
Yes
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 5, no count is 5

Test #5:

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

input:

1 1
0
10
0 0 1
0 0 1
0 0 1
0 0 1
0 0 1
0 0 1
0 0 1
0 0 1
0 0 1
0 0 1

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 10, no count is 0

Test #6:

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

input:

7 83382
35565 7347 27797 28072 31528 45377 43857
10
0 0 160004
0 0 224969
0 0 310304
0 0 354202
0 0 310303
0 0 493150
0 0 227687
0 0 448225
0 0 88396
0 0 155211

output:

No
No
Yes
Yes
No
Yes
No
Yes
No
No

result:

ok 10 token(s): yes count is 4, no count is 6

Test #7:

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

input:

7 83382
35212 3869 11565 53219 2927 45479 40671
10
0 0 189926
0 0 419739
0 0 245553
0 0 110218
0 0 299387
0 0 1986
0 0 473275
0 0 195521
0 0 299386
0 0 246039

output:

No
Yes
No
No
Yes
No
Yes
No
No
No

result:

ok 10 token(s): yes count is 3, no count is 7

Test #8:

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

input:

7 500000
6069 96930 28374 1275 53141 1423 6225
10
0 0 388080
0 0 73883
0 0 319880
0 0 141926
0 0 144641
0 0 67306
0 0 387304
0 0 387303
0 0 236649
0 0 130438

output:

Yes
No
No
No
No
No
Yes
No
No
No

result:

ok 10 token(s): yes count is 2, no count is 8

Test #9:

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

input:

7 500000
22379 39203 896 17806 23724 7599 153
10
0 0 492328
0 0 190173
0 0 315557
0 0 190172
0 0 138962
0 0 298883
0 0 246521
0 0 194070
0 0 252592
0 0 418531

output:

Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 8, no count is 2

Test #10:

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

input:

7 500000
0 0 0 0 0 0 0
10
0 0 124229
0 0 233729
0 0 306668
0 0 499999
0 0 220256
0 0 62117
0 0 115533
0 0 48137
0 0 160004
0 0 500000

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 10, no count is 0

Test #11:

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

input:

7 498000
498000 498000 498000 498000 498000 498000 498000
10
0 0 261154
0 0 235539
0 0 224636
0 0 283789
0 0 500000
0 0 480913
0 0 326331
0 0 499999
0 0 61700
0 0 280564

output:

No
No
No
No
No
No
No
No
No
No

result:

ok 10 token(s): yes count is 0, no count is 10

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #12:

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

input:

1 2
1
8
0 0 3
0 0 4
0 2 3
0 2 4
2 0 3
2 0 4
2 2 3
2 2 4

output:

No
Yes
No
Yes
No
Yes
No
Yes

result:

ok 8 token(s): yes count is 4, no count is 4

Test #13:

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

input:

1 2
1
10
0 1 1
0 1 2
2 1 1
2 1 2
1 0 2
1 0 3
1 2 2
1 2 3
1 1 1
1 1 500000

output:

No
Yes
No
Yes
No
Yes
No
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 6, no count is 4

Test #14:

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

input:

3 11
1 5 10
10
2 6 40
2 6 41
1 6 39
1 6 40
0 6 40
0 6 41
2 7 38
2 7 39
2 5 36
2 5 37

output:

No
Yes
No
Yes
No
Yes
No
Yes
No
Yes

result:

ok 10 token(s): yes count is 5, no count is 5

Test #15:

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

input:

3 1
0 1 1
8
0 0 6
0 0 7
1 1 5
1 1 6
0 1 4
0 1 5
1 0 5
1 0 6

output:

No
Yes
No
Yes
No
Yes
No
Yes

result:

ok 8 token(s): yes count is 4, no count is 4

Test #16:

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

input:

1 499999
499999
10
0 499999 500000
0 499999 499999
0 499999 499998
0 499999 499997
0 499999 499996
0 499999 5
0 499999 4
0 499999 3
0 499999 2
0 499999 1

output:

Yes
No
No
No
No
No
No
No
No
No

result:

ok 10 token(s): yes count is 1, no count is 9

Test #17:

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

input:

1 249999
0
10
0 249999 500000
0 249999 499999
0 249999 499998
0 249999 499997
0 249999 499996
0 249999 5
0 249999 4
0 249999 3
0 249999 2
0 249999 1

output:

Yes
Yes
No
No
No
No
No
No
No
No

result:

ok 10 token(s): yes count is 2, no count is 8

Test #18:

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

input:

3 2
2 1 0
10
0 2 1
0 2 2
0 2 3
0 2 4
0 2 5
0 2 6
0 2 7
0 2 8
0 2 8
0 2 8

output:

No
No
No
No
No
No
No
Yes
Yes
Yes

result:

ok 10 token(s): yes count is 3, no count is 7

Test #19:

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

input:

7 114381
99629 67979 86546 56087 63139 108255 68436
10
93017 26947 457994
68416 90149 398467
35162 8224 500000
93764 99122 353377
43358 112463 306282
26831 9795 500000
42369 15002 500000
6450 16746 500000
7483 81534 451399
104077 82098 359317

output:

No
No
No
No
Yes
No
No
No
Yes
Yes

result:

ok 10 token(s): yes count is 3, no count is 7

Test #20:

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

input:

7 156904
86214 84720 39018 38747 41086 17361 72963
10
20487 60246 473628
64601 77908 402948
131834 36311 458711
44757 12551 407379
137740 152086 500000
13822 41710 384936
54564 100719 445492
114985 55047 500000
93241 143516 500000
70481 91989 391569

output:

No
No
No
Yes
No
Yes
Yes
No
No
Yes

result:

ok 10 token(s): yes count is 4, no count is 6

Test #21:

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

input:

7 500000
250139 246072 286282 248011 246676 255434 285229
10
256986 250000 185280
249410 250000 192856
272916 250000 169350
248178 250000 194088
251192 250000 191073
282235 250000 160030
275248 250000 167017
286012 250000 156253
258808 250000 183458
281242 250000 161023

output:

Yes
Yes
Yes
Yes
No
No
No
No
Yes
No

result:

ok 10 token(s): yes count is 5, no count is 5

Test #22:

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

input:

7 500000
251721 246007 273667 246631 272904 242371 259470
10
259134 250000 187249
258860 250000 187524
266929 250000 179454
273220 250000 173163
264425 250000 181958
244659 250000 201725
262924 250000 183459
270049 250000 176334
252586 250000 193798
260138 250000 186246

output:

No
Yes
No
No
No
Yes
No
No
Yes
Yes

result:

ok 10 token(s): yes count is 4, no count is 6

Test #23:

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

input:

4 39
0 39 14 20
10
1 18 183
1 17 179
1 20 181
1 19 187
1 21 187
1 21 186
1 19 186
1 20 182
1 18 184
1 17 178

output:

No
Yes
No
Yes
Yes
No
No
Yes
Yes
No

result:

ok 10 token(s): yes count is 5, no count is 5

Test #24:

score: 0
Wrong Answer
time: 0ms
memory: 3556kb

input:

7 11559
11559 3854 5780 5459 0 5450 5395
10
1 5449 56325
1 5451 56325
1 5450 56317
1 5451 56324
1 5450 56316
1 5449 56324
1 5452 56318
1 5453 56310
1 5452 56319
1 5453 56311

output:

No
No
No
No
No
No
No
No
No
No

result:

wrong answer expected YES, found NO [1st token]

Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%