QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#487055 | #8257. Marathon Race 2 | bashkort | 7 | 0ms | 3832kb | C++20 | 4.2kb | 2024-07-22 15:39:31 | 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;
}
详细
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%