QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #71814 | #2974. 特技飞行 | He_Ren | 0 | 7ms | 9380kb | C++23 | 3.5kb | 2023-01-12 01:21:48 | 2023-01-12 01:23:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 5;
const int MAXQ = 1e5 + 5;
const int MAXD = 5e5 + 5;
struct BIT {
int tree[MAXD], n;
#define lowbit(x) ((x)&-(x))
inline void update(int x, int k) {
while (x <= n)
tree[x] += k,
x += lowbit(x);
}
inline void update(int l, int r, int k) {
update(l, k);
update(r + 1, -k);
}
inline int query(int x) {
int res = 0;
while (x)
res += tree[x],
x ^= lowbit(x);
return res;
}
} tree;
int begy[MAXN], enny[MAXN];
int fa[MAXN];
int find(int u) {
return fa[u] == u ? u : fa[u] = find(fa[u]);
}
int main(void) {
freopen("aero6.in", "r", stdin);
int n, A, B, C, begx, ennx;
scanf("%d%d%d%d%d%d", &n, &A, &B, &C, &begx, &ennx);
for (int i = 1; i <= n; ++i)
scanf("%d", &begy[i]);
for (int i = 1; i <= n; ++i)
scanf("%d", &enny[i]);
const ll BASE = 1e10;
set<pii> t;
vector< pair<ll, ll>> pt;
for (int i = n; i >= 1; --i) {
auto it = t.begin();
for (; it != t.end() && it -> first < enny[i]; ++it) {
int j = it -> second;
ldb
k1 = (ldb)(enny[i] - begy[i]) / (ennx - begx),
k2 = (ldb)(enny[j] - begy[j]) / (ennx - begx),
dx = (begy[j] - begy[i]) / (k1 - k2),
x = begx + dx,
y = begy[i] + dx * k1;
pt.emplace_back(round((x + y) * BASE), round((x - y) * BASE));
}
t.emplace_hint(it, enny[i], i);
}
static ll dsc[MAXD];
int dcnt = 0;
for (auto it : pt)
dsc[++dcnt] = it.second;
sort(dsc + 1, dsc + dcnt + 1);
dcnt = unique(dsc + 1, dsc + dcnt + 1) - dsc - 1;
int Q;
scanf("%d", &Q);
vector< tuple<ll, int, int, int>> eff;
while (Q--) {
int x, y, r;
scanf("%d%d%d", &x, &y, &r);
tie(x, y) = make_tuple(x + y, x - y);
int yl = lower_bound(dsc + 1, dsc + dcnt + 1, (y - r) * BASE) - dsc;
int yr = upper_bound(dsc + 1, dsc + dcnt + 1, (y + r) * BASE) - dsc - 1;
if (yl > yr)
continue;
eff.emplace_back((x - r) * BASE, 1, yl, yr);
eff.emplace_back((x + r) * BASE + 1, 2, yl, yr);
}
int useC = 0;
tree.n = dcnt;
sort(pt.begin(), pt.end());
sort(eff.begin(), eff.end());
for (int i = 0, j = 0; i < (int)pt.size(); ++i) {
for (; j < (int)eff.size() && get<0>(eff[j]) <= pt[i].first; ++j)
tree.update(get<2>(eff[j]), get<3>(eff[j]), get<1>(eff[j]) == 1 ? 1 : -1);
int cury = lower_bound(dsc + 1, dsc + dcnt + 1, pt[i].second) - dsc;
if (tree.query(cury))
++useC;
}
static int ord[MAXN];
iota(ord + 1, ord + n + 1, 1);
sort(ord + 1, ord + n + 1, [&](int x, int y) {
return enny[x] < enny[y];
});
iota(fa + 1, fa + n + 1, 1);
int ccnt = n;
for (int i = 1; i <= n; ++i)
if (find(i) != find(ord[i])) {
--ccnt;
fa[find(i)] = find(ord[i]);
}
int cr = (int)pt.size();
int must = n - ccnt;
ll ans1 = (ll)cr * A, ans2 = (ll)must * A + (ll)(cr - must) * B;
ans1 += (ll)useC * C;
ans2 += (ll)useC * C;
if (ans1 > ans2)
swap(ans1, ans2);
printf("%lld %lld", ans1, ans2);
return 0;
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
input:
15 62 75 98 0 150 93 159 202 209 277 317 383 461 556 600 650 657 737 762 783 45 98 251 377 368 172 600 621 495 625 57 264 415 318 534 15 78 421 8 38 411 5 89 279 13 87 468 6 72 430 3 70 320 5 52 418 6 79 446 15 79 469 4 70 576 1 74 243 6 99 386 13 37 285 6 52 421 5 110 541 2
output:
result:
Test #2:
score: 0
Runtime Error
input:
15 96 82 69 0 150 26 86 99 130 138 194 218 312 394 436 445 467 522 574 614 281 361 527 12 573 825 264 94 388 625 429 364 183 711 767 15 72 236 11 70 614 14 44 506 1 37 225 13 97 456 14 97 423 14 107 338 12 82 537 7 94 396 1 67 570 1 73 375 5 86 471 1 39 356 7 111 272 8 87 416 1
output:
result:
Test #3:
score: 0
Runtime Error
input:
15 9 17 92 0 150 95 177 269 332 432 531 631 648 655 723 757 805 836 936 983 381 113 198 265 694 431 100 609 788 772 282 835 387 529 320 15 40 364 3 87 299 6 37 345 10 81 729 8 43 592 2 64 582 12 92 339 7 50 534 1 42 444 1 97 410 1 87 476 9 49 312 1 51 276 11 77 475 10 87 248 8
output:
result:
Test #4:
score: 0
Wrong Answer
time: 7ms
memory: 7428kb
input:
15 82 51 38 0 150 1 45 51 76 119 185 212 221 224 280 356 396 419 472 481 123 51 514 438 320 191 530 462 611 8 144 340 220 558 573 15 42 184 6 92 374 7 79 275 7 111 208 13 64 441 6 46 447 6 104 165 14 88 340 1 106 286 1 67 265 8 77 277 13 74 355 12 40 359 13 108 309 10 76 154 6
output:
-53193767583768 0
result:
wrong answer 1st lines differ - expected: '2468 3274', found: '-53193767583768 0'
Test #5:
score: 0
Runtime Error
input:
20000 735 614 787 0 1000000 271 611 909 1076 1306 1406 1864 1902 2176 2538 2898 3207 3283 3453 3483 3490 3876 4033 4367 4827 5075 5296 5401 5700 5798 6293 6333 6615 6988 7102 7109 7482 7856 8154 8239 8631 9100 9177 9505 9720 10162 10275 10356 10391 10602 11012 11311 11493 11887 12287 12532 13031 132...
output:
result:
Test #6:
score: 0
Wrong Answer
time: 1ms
memory: 7328kb
input:
30000 819 703 768 1 1500000 72 485 920 1000 1023 1364 1792 2210 2259 2540 2595 3019 3066 3132 3627 3939 4318 4380 4389 4436 4495 4927 4960 5094 5131 5599 5639 5971 6263 6660 6766 7185 7674 7861 7892 8210 8259 8737 9231 9626 9856 9884 10138 10295 10479 10749 10758 11070 11412 11774 11848 11952 11962 ...
output:
-55741475279494 0
result:
wrong answer 1st lines differ - expected: '109195803 121700139', found: '-55741475279494 0'
Test #7:
score: 0
Runtime Error
input:
30000 984 515 554 12306 1500000 67 338 466 566 993 1028 1478 1636 1767 2151 2276 2587 2828 3075 3305 3774 4199 4456 4890 5377 5756 6159 6492 6940 7037 7324 7813 7862 7891 8256 8338 8664 8667 8745 9068 9300 9613 9908 9973 10035 10211 10619 10810 11003 11114 11140 11413 11683 11697 11914 12139 12465 1...
output:
result:
Test #8:
score: 0
Wrong Answer
time: 4ms
memory: 7372kb
input:
30000 791 883 894 999 1500000 24 381 828 1259 1346 1401 1885 2232 2242 2346 2823 3282 3725 3781 3822 4177 4194 4356 4743 5050 5244 5376 5502 5887 6086 6305 6671 6797 6870 7260 7748 7812 7950 8148 8633 9100 9219 9301 9719 9897 9917 10177 10311 10407 10655 11074 11152 11342 11417 11419 11824 12107 124...
output:
-17587841570442 0
result:
wrong answer 1st lines differ - expected: '119138650 129076490', found: '-17587841570442 0'
Test #9:
score: 0
Time Limit Exceeded
input:
100000 159 159 177 0 5000000 285 706 1409 1993 2211 3102 3573 3788 4701 5499 6017 6767 7629 7678 8196 8642 9343 9517 10272 10526 11310 12065 12881 13778 14099 14241 14989 15515 15594 16469 16618 17202 17822 18217 18380 19020 19026 19129 19665 19728 20260 20345 20888 21176 21396 22374 22473 22934 230...
output:
result:
Test #10:
score: 0
Wrong Answer
time: 3ms
memory: 7288kb
input:
100000 163 163 118 0 5000000 93 520 633 645 719 1588 2514 2796 3785 4478 4565 4936 5045 5446 5857 6278 6450 7091 7440 8254 8322 8745 9572 10016 10571 10946 11364 12045 12599 12930 13905 13939 14661 15215 15216 15360 15520 15778 16248 16566 16737 17156 17183 17922 18773 18875 19291 19710 19762 20040 ...
output:
-2770786653630 0
result:
wrong answer 1st lines differ - expected: '92520830 92520830', found: '-2770786653630 0'
Test #11:
score: 0
Runtime Error
input:
100000 196 196 136 0 10000000 11 151 426 1181 1379 1664 2010 2210 3206 3493 4156 4766 5219 6115 6226 6241 7159 7347 8236 8673 9257 9863 9901 10256 10494 11488 11523 12365 13041 13474 14407 15196 15434 16318 17290 17297 18256 18325 18840 19292 19440 20338 21025 21884 22172 22359 23244 23694 24527 252...
output:
result:
Test #12:
score: 0
Wrong Answer
time: 4ms
memory: 7344kb
input:
100000 111 111 110 0 10000000 113 933 1711 2333 2581 3372 4041 4710 4795 4824 5438 5845 5983 6709 7516 8121 8779 9559 10498 10576 10890 11872 12332 13245 13949 14700 14734 15614 16047 16933 17385 17887 18286 18605 19385 20019 20614 21368 22358 22458 22625 22627 22988 23283 23419 24252 24437 25380 25...
output:
-17174387495240 0
result:
wrong answer 1st lines differ - expected: '68751012 68751012', found: '-17174387495240 0'
Test #13:
score: 0
Wrong Answer
time: 4ms
memory: 9380kb
input:
50000 167 102 130 0 5000000 531 999 1117 1394 1538 1717 2492 3466 3539 3789 3791 4125 4927 5136 5934 6680 7318 7815 8108 8113 8178 8301 8395 8497 9441 9660 10209 10916 11155 11750 12132 12929 13076 13433 14067 14488 14850 15370 16195 16315 16459 16506 16563 16930 17854 18069 18714 18828 19622 20166 ...
output:
0 38263079589000
result:
wrong answer 1st lines differ - expected: '36739725 48444145', found: '0 38263079589000'
Test #14:
score: 0
Wrong Answer
time: 4ms
memory: 7300kb
input:
50000 156 126 168 0 5000000 504 1157 1623 2246 3181 3794 3965 4092 4688 5002 5139 5381 6301 6675 7622 8089 8309 8382 9368 9843 10341 11104 11363 11548 11766 12041 13036 13427 13505 13809 14061 14676 14974 15110 15742 16228 16891 17675 18214 19070 19877 20865 21126 21690 22104 22375 23199 23256 23455...
output:
0 25498886088962
result:
wrong answer 1st lines differ - expected: '43758636 49151136', found: '0 25498886088962'
Test #15:
score: 0
Wrong Answer
time: 4ms
memory: 7372kb
input:
50000 157 165 142 0 5000000 196 1126 1999 2258 2379 2642 2791 3380 3761 4056 4629 5116 5597 5718 6388 6936 7031 7815 7992 8788 8934 9389 9779 9821 10566 11425 11589 12391 13228 13981 14537 15031 15440 15746 16642 17493 18375 18554 19047 19855 20157 20207 20391 21134 21400 22255 22464 23319 23741 241...
output:
0 7237638431913
result:
wrong answer 1st lines differ - expected: '47159963 48597003', found: '0 7237638431913'
Test #16:
score: 0
Wrong Answer
time: 4ms
memory: 7280kb
input:
50000 173 189 160 0 5000000 75 627 1611 1957 2029 2681 3076 3281 3613 4419 5021 5074 5952 6449 6834 7174 7469 8301 8952 9503 10029 10611 11292 11309 11812 12428 13234 13455 13579 14091 14404 14887 15320 15443 16270 17248 18222 19075 19589 20213 21126 21649 22605 22907 23373 23631 23991 24495 25426 2...
output:
0 30520730648486
result:
wrong answer 1st lines differ - expected: '52275056 55149200', found: '0 30520730648486'
Test #17:
score: 0
Runtime Error
input:
100000 464 494 610 0 10000000 689 815 1263 2049 2139 3032 3991 4651 5007 5541 5827 5955 6536 6767 7504 8168 8205 8941 9818 10428 11301 11367 11406 11780 12571 12909 13101 13952 14435 14688 15599 16113 16354 16480 16631 17289 18286 18604 19398 19644 20228 20791 21517 21593 21604 22064 23032 23360 235...
output:
result:
Test #18:
score: 0
Wrong Answer
time: 7ms
memory: 7420kb
input:
100000 65 916 40 0 10000000 117 1094 1639 2424 2425 3195 3729 3858 4094 4222 4973 4984 5674 6339 6727 6931 7318 7661 8499 8743 9408 10053 11005 11214 11279 11871 12804 13799 13963 14955 15029 15988 16090 16857 17110 18102 18356 19109 19748 19943 20135 21028 21602 22220 22275 22574 23228 23296 23343 ...
output:
0 43467796511440
result:
wrong answer 1st lines differ - expected: '36085925 342604211', found: '0 43467796511440'
Test #19:
score: 0
Runtime Error
input:
100000 122 832 107 0 10000000 590 661 1114 1460 2267 2510 2944 3671 3895 4408 4778 5613 5866 6820 7405 7994 8880 9330 9712 9874 10091 11028 11570 11768 12603 12670 13506 13618 14499 15494 15875 16572 17384 17875 18391 19028 19800 20791 21120 21923 22735 22858 23242 23876 24714 25491 26162 26926 2754...
output:
result:
Test #20:
score: 0
Runtime Error
input:
100000 154 478 421 0 10000000 407 1174 1178 1630 1633 1652 1782 2380 3287 4091 5052 5799 6792 7727 7953 8646 8995 9192 9902 10773 11060 11487 11612 12164 12313 12656 13305 13782 14319 15104 15986 16124 16787 17633 17748 18548 19449 19924 20009 20687 21075 22059 22886 23151 23910 24240 24733 24787 25...