QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#247651 | #4583. Concerto de Pandemic | warner1129 | WA | 868ms | 51412kb | C++20 | 3.1kb | 2023-11-11 15:19:47 | 2023-11-11 15:19:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
template<class... T> void dbg(T... x) { char e{}; ((cerr << e << x, e = ' '), ...); }
template<class T> void org(T l, T r) { while (l != r) cerr << ' ' << *l++; cerr << '\n'; }
#define debug(x...) dbg(#x, '=', x, '\n')
#define olist(x...) dbg(#x, '='), org(x)
#else
#define debug(...) ((void)0)
#define olist(...) ((void)0)
#endif
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ff first
#define ss second
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
constexpr int inf = 1e9;
constexpr int mod = 998244353;
template<class T> bool chmin(T &a, T b) { return (b < a and (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b and (a = b, true)); }
template<class... T> int add(T... x) { int t{}; return (((t += x) %= mod), ...), t; }
template<class... T> int mul(T... x) { i64 t{1}; return (((t *= x) %= mod), ...), t; }
void solve() {
int n, m, K, P;
cin >> n >> m >> K >> P;
vector<i64> dis(n, 1);
vector<bool> blk(n);
for (int i = 0; i < m; i++) {
int c, t;
cin >> c >> t;
c--;
dis[c] += t;
blk[c] = true;
}
partial_sum(all(dis), dis.begin());
vector<bool> fan(n);
for (int i = 0; i < K; i++) {
int x;
cin >> x;
fan[x - 1] = true;
}
vector<i64> D;
vector<bool> F;
for (int i = 0; i < n; i++)
if (!blk[i]) {
F.push_back(fan[i]);
D.push_back(dis[i]);
}
n = F.size();
const int H = __lg(n);
for (int i = 0; i < n * 2; i++) {
F.push_back(F[i]);
D.push_back(D[i] + dis.back());
}
olist(all(F));
olist(all(D));
auto check = [&](i64 C) -> bool {
vector<int> L(n * 3);
vector<int> tag(n * 3 + 1, n * 3);
for (int l = 0, r = 0; l < n * 3; l++) {
while (r < n * 3 and r - l < n and D[r] - D[l] <= C) {
L[r] = l;
r++;
}
if (n <= l and l < n * 2 and F[l]) {
chmin(tag[L[l]], min(L[l] + n, r));
}
}
vector st(H + 1, vector<int>(n * 3 + 1, n * 3));
for (int i = n * 3 - 1; i >= 0; i--) {
chmin(tag[i], tag[i + 1]);
st[0][i] = tag[i];
}
for (int i = 0; i + 1 < H + 1; i++)
for (int j = 0; j < n * 3; j++) {
st[i + 1][j] = st[i][st[i][j]];
}
for (int i = 0; i < n * 2; i++) {
int p = i;
int s = 0;
for (int j = H; j >= 0; j--)
if (st[j][p] <= i + n) {
p = st[j][p];
s += (1 << j);
}
if (s > P) return true;
}
return false;
};
i64 ans = *ranges::partition_point(views::iota(0ll, (i64)1e18), check);
cout << ans << '\n';
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
cin.exceptions(cin.failbit);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3628kb
input:
10 4 3 2 1 2 4 4 6 2 7 5 2 5 8
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
8 1 3 5 1 5 4 2 7
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
5 2 2 1 1 14 2 14 3 5
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
2 1 1 1 1 200000 2
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 503ms
memory: 24712kb
input:
190976 113222 55610 23475 51263 120558 10007 171596 46671 108981 117183 169457 18187 84735 149298 124718 79376 129184 28117 76880 109791 87521 114840 59510 38014 178362 41701 11344 27561 192741 173835 54534 71368 76692 122745 95537 152595 158352 43901 162441 98927 105784 22484 96000 19443 113614 370...
output:
170531
result:
ok single line: '170531'
Test #6:
score: 0
Accepted
time: 868ms
memory: 51412kb
input:
198722 26425 169256 110599 33948 74442 51729 66300 40369 173859 42274 73043 117803 108716 149794 151005 147161 2675 148063 166634 132585 51612 141999 182365 32951 159790 120932 290 82655 150138 49337 10396 171146 129572 33311 193079 195115 171691 180568 77905 65397 110312 156436 149966 9377 55490 12...
output:
1
result:
ok single line: '1'
Test #7:
score: 0
Accepted
time: 231ms
memory: 17212kb
input:
200000 150000 50000 24998 187150 200000 81420 200000 167617 200000 100616 200000 135362 200000 156943 200000 83069 200000 48837 200000 179969 200000 138130 200000 133131 200000 196045 200000 169575 200000 163857 200000 106717 200000 191966 200000 131394 200000 145647 200000 160212 200000 75181 20000...
output:
200002
result:
ok single line: '200002'
Test #8:
score: 0
Accepted
time: 211ms
memory: 17236kb
input:
200000 150000 50000 2 99352 200000 85760 200000 126279 200000 78681 200000 191980 200000 123278 200000 90780 200000 183926 200000 92668 200000 92156 200000 157074 200000 104604 200000 87593 200000 183454 200000 38009 200000 132806 200000 96071 200000 135445 200000 123768 200000 80039 200000 199215 2...
output:
1250012500
result:
ok single line: '1250012500'
Test #9:
score: 0
Accepted
time: 26ms
memory: 4792kb
input:
200000 199999 1 1 44417 200000 47743 200000 134710 200000 118852 200000 9605 200000 150296 200000 80589 200000 3336 200000 66496 200000 90172 200000 190899 200000 3355 200000 107595 200000 111949 200000 146872 200000 72419 200000 115626 200000 127077 200000 173509 200000 194749 200000 109608 200000 ...
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 468ms
memory: 31256kb
input:
200000 100000 100000 25746 186550 200000 85622 200000 21024 200000 59750 200000 76456 200000 87534 200000 76522 200000 103422 200000 165806 200000 138372 200000 166050 200000 176354 200000 15168 200000 69928 200000 187102 200000 130486 200000 182278 200000 161502 200000 95032 200000 119864 200000 17...
output:
400004
result:
ok single line: '400004'
Test #11:
score: 0
Accepted
time: 26ms
memory: 4768kb
input:
200000 199990 10 9 185044 200000 96615 200000 172973 200000 82849 200000 162889 200000 59668 200000 20522 200000 193263 200000 70559 200000 140931 200000 147680 200000 26312 200000 133330 200000 74332 200000 149589 200000 61277 200000 173461 200000 152403 200000 174666 200000 56706 200000 9288 20000...
output:
3865019326
result:
ok single line: '3865019326'
Test #12:
score: 0
Accepted
time: 21ms
memory: 4644kb
input:
200000 199998 2 1 67932 200000 165398 200000 653 200000 12879 200000 179014 200000 173052 200000 19237 200000 31754 200000 83892 200000 67089 200000 172429 200000 20736 200000 19809 200000 195941 200000 165861 200000 192485 200000 50670 200000 154401 200000 183669 200000 160442 200000 96158 200000 4...
output:
19999900000
result:
ok single line: '19999900000'
Test #13:
score: 0
Accepted
time: 220ms
memory: 17224kb
input:
200000 150000 50000 14589 9852 200000 146233 200000 81635 200000 153688 200000 180401 200000 131217 200000 147689 200000 175789 200000 157008 200000 82379 200000 197870 200000 158300 200000 136907 200000 90916 200000 133283 200000 115911 200000 178151 200000 52380 200000 125603 200000 17720 200000 5...
output:
400004
result:
ok single line: '400004'
Test #14:
score: 0
Accepted
time: 183ms
memory: 17200kb
input:
200000 150000 50000 3 92863 200000 143656 200000 177807 200000 82115 200000 127226 200000 153355 200000 195151 200000 183196 200000 56488 200000 105395 200000 174745 200000 9192 200000 122947 200000 102569 200000 71127 200000 198334 200000 140867 200000 91775 200000 176858 200000 78928 200000 116317...
output:
1666816667
result:
ok single line: '1666816667'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
10 2 2 4 1 45 9 45 5 6
output:
0
result:
ok single line: '0'
Test #16:
score: 0
Accepted
time: 137ms
memory: 11068kb
input:
184056 156924 27132 5487 31071 76922 182522 95921 153369 55991 171710 52252 41681 88855 80541 147855 17375 23664 166681 99712 85334 139650 91006 107711 183992 133132 18219 116694 10973 36327 29655 3541 9566 121602 20135 150626 165572 199426 34139 114077 172106 9046 111675 183349 52859 2653 162895 48...
output:
1391357
result:
ok single line: '1391357'
Test #17:
score: 0
Accepted
time: 630ms
memory: 35576kb
input:
198946 85509 113437 16454 55928 11746 151106 176741 67787 119235 6964 121879 87064 105123 182446 67770 148232 164626 84669 181152 177124 116910 124895 83907 65566 65423 153714 197476 67769 108011 8201 139194 91192 80237 84858 168819 73079 185222 55701 151129 60694 17931 179882 117777 154826 119669 1...
output:
251741
result:
ok single line: '251741'
Test #18:
score: 0
Accepted
time: 22ms
memory: 4620kb
input:
184845 184844 1 1 159765 128047 129626 3304 35698 88302 142782 113626 46033 196503 94300 101851 148700 52627 101827 122109 34448 104944 94260 154823 32130 48872 72954 199176 50529 151953 53369 38890 35837 195530 107050 68183 105336 41797 127928 74999 144029 51097 16189 75339 119777 179826 94102 1624...
output:
0
result:
ok single line: '0'
Test #19:
score: 0
Accepted
time: 19ms
memory: 4668kb
input:
183091 183090 1 1 12308 23858 135357 5256 150368 37499 118187 37965 54415 24892 125817 38590 81315 186626 13463 164488 136540 24565 145451 98230 130596 163280 80257 160167 131667 188684 43557 68858 77488 104306 25073 144258 104735 157480 23991 28887 67302 68251 127993 120450 93683 52143 127786 13219...
output:
0
result:
ok single line: '0'
Test #20:
score: 0
Accepted
time: 23ms
memory: 4788kb
input:
185561 185559 2 1 97801 136363 66008 136066 173944 59291 84394 162605 136281 88025 155011 701 184637 86732 87309 98378 70530 162334 162566 153674 158032 185895 127014 172074 65742 28387 102936 28533 84549 125060 652 51442 70185 182692 1996 112759 101772 21021 34755 15804 92317 146543 97125 153712 13...
output:
1579892162
result:
ok single line: '1579892162'
Test #21:
score: 0
Accepted
time: 20ms
memory: 4788kb
input:
183182 183180 2 1 63223 3168 141520 69479 102948 133687 168811 61676 1040 131270 96738 46087 44583 80530 34917 198354 143916 73083 90118 136430 143264 19353 102753 197144 4376 71023 132710 140871 61456 141299 39456 46272 36213 130567 156330 173816 154675 195443 14550 106176 147487 91753 77544 28222 ...
output:
7692313709
result:
ok single line: '7692313709'
Test #22:
score: 0
Accepted
time: 25ms
memory: 4664kb
input:
195431 195367 64 30 36156 60535 180283 153306 192146 194701 124139 127831 76060 17748 148550 69471 69448 1188 179162 186722 188498 44999 11250 67523 27826 144158 191515 18496 127589 12954 127966 24839 9285 26855 110964 28073 167740 98491 65303 92934 162830 75852 64299 156312 61352 100260 172221 7723...
output:
287022566
result:
ok single line: '287022566'
Test #23:
score: 0
Accepted
time: 22ms
memory: 4612kb
input:
195507 195443 64 28 107028 104100 106907 193032 45258 195130 168641 198440 90592 198719 31617 88887 72796 79245 41191 20722 53917 159740 34173 21748 127611 171540 186506 92330 189538 141942 41574 122048 69615 93751 59046 89045 176461 111632 74703 8471 5065 42899 1888 179533 150575 88597 72116 37233 ...
output:
302878794
result:
ok single line: '302878794'
Test #24:
score: 0
Accepted
time: 26ms
memory: 4960kb
input:
184543 183830 713 203 108924 161080 101919 104871 50685 182714 52699 74184 180944 142023 55277 4859 4461 153623 141162 149967 8865 72164 148155 80178 10817 75920 2978 41235 7205 55147 13738 2734 171075 142707 115453 95060 31261 172373 86949 71831 32714 5579 53948 168389 485 99005 121956 131933 11897...
output:
42317159
result:
ok single line: '42317159'
Test #25:
score: 0
Accepted
time: 22ms
memory: 4964kb
input:
189799 189086 713 111 41639 177678 133461 10900 13692 152687 185198 182955 17643 5391 139287 15315 99971 126465 30778 73425 144220 183083 102181 95818 4416 13181 67758 117233 17022 49027 156528 184034 150532 173950 60128 35969 143614 82248 162094 92672 94051 127859 19768 130931 50065 62212 28095 132...
output:
81374116
result:
ok single line: '81374116'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
4 2 2 1 1 2 3 2 2 4
output:
4
result:
ok single line: '4'
Test #27:
score: 0
Accepted
time: 28ms
memory: 5256kb
input:
182652 180020 2632 427 148103 28327 118881 143601 66544 93306 98324 88713 111079 141633 137208 24194 94888 188951 272 70612 118701 128800 67012 121878 32737 133925 161758 101003 57546 68806 112070 90206 103631 170676 132438 78285 112805 166403 45911 172555 145479 96958 159030 100240 30297 89145 7512...
output:
20954707
result:
ok single line: '20954707'
Test #28:
score: 0
Accepted
time: 33ms
memory: 5416kb
input:
198844 196212 2632 735 78461 167318 118429 157481 141228 199462 168970 120477 48125 87282 88870 190003 24595 22332 33767 186866 142932 36313 113726 46047 138880 51749 42038 193616 12754 154506 144684 13867 33847 20778 2628 78074 152674 44161 136007 140434 6442 183542 176716 151126 124899 93285 9788 ...
output:
12810308
result:
ok single line: '12810308'
Test #29:
score: 0
Accepted
time: 378ms
memory: 22800kb
input:
189610 119689 69921 5991 164960 7372 178298 92501 49043 122790 4949 141312 6688 19818 110244 53106 37455 147574 187994 134897 176097 166967 45890 169799 102327 118838 7199 109268 29167 66183 156290 196754 175268 121900 56409 80971 117030 34287 16346 33801 111951 467 86336 90748 120982 145426 155859 ...
output:
995854
result:
ok single line: '995854'
Test #30:
score: 0
Accepted
time: 433ms
memory: 22824kb
input:
181153 111232 69921 14891 61153 187956 81419 72744 80967 100067 128595 124185 38436 112881 66913 26052 156254 67588 87223 83823 47660 106990 4479 21237 129684 86007 134966 169981 25178 57652 90184 42558 116245 167189 136200 70697 19251 43067 11523 54079 58693 148387 113897 82626 130603 25056 84720 1...
output:
352086
result:
ok single line: '352086'
Test #31:
score: 0
Accepted
time: 370ms
memory: 21760kb
input:
187670 121624 66046 40220 85947 180988 142838 38976 77666 147901 166637 51007 147090 37075 158080 56050 124234 190040 18136 4422 170815 139856 56047 88348 61317 108670 177199 39817 47663 155319 99556 189269 7659 48517 135859 129790 73269 95600 15591 1249 89545 92438 143046 180286 1593 71318 16779 12...
output:
32418
result:
ok single line: '32418'
Test #32:
score: 0
Accepted
time: 613ms
memory: 34180kb
input:
185665 76666 108999 102379 82751 129276 170767 6258 51779 92897 4415 105658 51875 194398 12614 116050 1457 58872 184476 178587 72266 40479 112888 174833 128404 132114 176724 157832 100491 163419 106710 103082 9479 37696 77430 111356 35587 29434 4861 140402 145375 50650 28288 163050 119709 160000 183...
output:
1
result:
ok single line: '1'
Test #33:
score: 0
Accepted
time: 625ms
memory: 30188kb
input:
180016 82053 97963 45780 44951 129698 5995 40353 137012 45586 61149 141943 118870 129916 129797 16588 37808 107029 169839 182878 113777 65601 11 96478 4513 164369 75569 65964 78575 180841 37756 59222 155499 35167 6636 165955 105326 41660 157174 28809 38040 22098 127757 126029 168370 50812 84664 1595...
output:
3
result:
ok single line: '3'
Test #34:
score: -100
Wrong Answer
time: 410ms
memory: 23844kb
input:
186895 112521 74374 1 177659 27707 75115 2987 16384 36906 129595 166103 7346 143245 59382 114280 186691 84440 13076 78300 161731 23662 32098 31484 90029 119182 179235 126045 147032 185998 173318 161230 18246 65427 53887 134126 50968 132426 114943 18662 148085 99748 65603 94694 110581 191032 159157 1...
output:
2817187054
result:
wrong answer 1st lines differ - expected: '5631712881', found: '2817187054'