QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#703894 | #5417. Chat Program | Kdlyh | TL | 2853ms | 13864kb | C++20 | 4.8kb | 2024-11-02 18:48:30 | 2024-11-02 18:48:32 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <stack>
using namespace std;
#ifdef LOCAL
template <class T, size_t size = std::tuple_size<T>::value> std::string to_debug(T, std::string s = "") requires(not std::ranges::range<T>);
std::string to_debug(auto x) requires requires(std::ostream& os) { os << x; } { return static_cast<std::ostringstream>(std::ostringstream() << x).str(); }
std::string to_debug(std::ranges::range auto x, std::string s = "") requires(not std::is_same_v<decltype(x), std::string>) {
for (auto xi : x) { s += ", " + to_debug(xi); }
return "[" + s.substr(s.empty() ? 0 : 2) + "]";
}
template <class T, size_t size> std::string to_debug(T x, std::string s) requires(not std::ranges::range<T>) {
[&]<size_t... I>(std::index_sequence<I...>) { ((s += ", " + to_debug(get<I>(x))), ...); }(std::make_index_sequence<size>());
return "(" + s.substr(s.empty() ? 0 : 2) + ")";
}
#define debug(...) std::cerr << __LINE__ << ": (" #__VA_ARGS__ ") = " << to_debug(std::tuple(__VA_ARGS__)) << "\n"
#else
#define debug(x...)
#endif
using i64 = long long;
template<class T>
struct Discreater {
std::vector<T> elementSet;
Discreater(const std::vector<T> &a) : elementSet(a) {
sort(begin(elementSet), end(elementSet));
elementSet.erase(unique(begin(elementSet), end(elementSet)), end(elementSet));
}
vector<int> process(const vector<T>& a) const {
vector<int> disRes(size(a));
for (int i = 0; i < size(a); i++) {
disRes[i] = query(a[i]);
}
return disRes;
}
int query(const T& x) const {
auto it{lower_bound(begin(elementSet), end(elementSet), x)};
return it - begin(elementSet);
}
T queryInv(int index) const {
return elementSet[index];
}
int getSize() {return (int)size(elementSet);}
};
inline int __lg(int __n) { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); }
template<typename T>
struct Fenwick {
int n;
vector<T> a;
Fenwick(int n_ = 0) {init(n_);}
void init(int n_) {n = n_; a.assign(n, T{});}
void add(int x, const T& v) {
for (int i = x + 1; i <= n; i += i & -i) {
a[i - 1] = a[i - 1] + v;
}
}
T sum(int x) {
T ans{};
for (int i = x; i > 0; i -= i & -i) {
ans = ans + a[i - 1];
}
return ans;
}
T rangeSum(int l, int r) {
return sum(r) - sum(l);
}
};
void solve()
{
int n, k, m, c, d; std::cin >> n >> k >> m >> c >> d;
vector<i64> a(n); for (auto& ai : a) {std::cin >> ai;}
vector<i64> da{a}; i64 add{}; for (int i = 0; i < n; i++) {da[i] += add; add += d;}
auto check = [&](i64 T) {//大于等于 T - c, T - c + d, T - c + 2d... 的数
//扔入离散化
vector<i64> initHC{da};
{
i64 tar{T - c}; for (int i = 0; i < n - m + 1; i++) {initHC.push_back(tar); tar += d;} initHC.push_back(T);
}
Discreater<i64> discreaterHC(initHC);//给滑窗init
const int OPHC{discreaterHC.getSize() + 1};
Fenwick<int> segtHC(OPHC);
//说白了, YS 就是要比较滑窗外 ai >= T 的个数
for (int i = 0; i < m; i++) {segtHC.add(discreaterHC.query(da[i]), 1);}
int cntYS{}; for (int i = m; i < n; i++) {cntYS += (a[i] >= T);}
i64 tarHC{T - c}, tarYS{T}; for (int r = m; r < n; r++) {
int cntHC{segtHC.rangeSum(discreaterHC.query(tarHC), OPHC)};
if (cntHC + cntYS >= k) {return true;}
cntYS -= (a[r] >= tarYS);
cntYS += (a[r - m] >= tarYS);
segtHC.add(discreaterHC.query(da[r]), 1);
segtHC.add(discreaterHC.query(da[r - m]), -1);
tarHC += d;
}
if (segtHC.rangeSum(discreaterHC.query(tarHC), OPHC) + cntYS >= k) {
return true;
}
return false;
};
i64 lo{}, hi{(i64)1E15}; while (lo <= hi) {
i64 mid{lo + hi >> 1}; check(mid) ? lo = mid + 1 : hi = mid - 1;
}
i64 ans{lo - 1};
sort(rbegin(a), rend(a)); ans = std::max(ans, a[k - 1]);
std::cout << ans << "\n";
}
signed main()
{
std::cin.tie(nullptr)->sync_with_stdio(false);
int _{1};
#ifdef tests
std::cin >> _;
#endif
while(_--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
input:
6 4 3 1 2 1 1 4 5 1 4
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
7 3 2 4 0 1 9 1 9 8 1 0
output:
9
result:
ok 1 number(s): "9"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
8 3 5 0 0 2 0 2 2 1 2 1 8
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 2129ms
memory: 12540kb
input:
200000 200000 100000 0 1000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 1556ms
memory: 12620kb
input:
200000 1 100000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 100000000...
output:
100001000000000
result:
ok 1 number(s): "100001000000000"
Test #6:
score: 0
Accepted
time: 777ms
memory: 11960kb
input:
200000 1 200000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 100000000...
output:
200001000000000
result:
ok 1 number(s): "200001000000000"
Test #7:
score: 0
Accepted
time: 2853ms
memory: 13864kb
input:
200000 24420 17993 881138881 700368758 231187558 519018952 260661004 740633836 931672020 155904999 647179942 13217847 779799803 382810661 242588977 708308843 309853544 225488875 389115097 588643904 644409212 704920939 231829287 39891424 881158891 341251089 486868469 808002305 629160633 317239613 771...
output:
964474978
result:
ok 1 number(s): "964474978"
Test #8:
score: 0
Accepted
time: 2646ms
memory: 13560kb
input:
200000 31878 34175 753689504 94554240 764252685 385025201 185233994 886343186 532991571 477855721 681289648 908112797 112162074 199451201 408329780 674092805 896613552 521026518 597166827 166901445 503106595 958954753 464273450 431481790 32269637 998211679 557906218 821269178 46577165 394469258 5350...
output:
218913332405
result:
ok 1 number(s): "218913332405"
Test #9:
score: 0
Accepted
time: 2002ms
memory: 12988kb
input:
200000 66779 68097 331272836 488739723 665914031 251031451 773370496 810714172 839343832 504839150 83995574 139444234 739491638 942462815 647699510 49942183 188406268 595225798 436622337 155224403 656771269 212988566 991684904 118039448 141911186 286576049 628943968 834536050 463993698 103102683 298...
output:
645490226257
result:
ok 1 number(s): "645490226257"
Test #10:
score: 0
Accepted
time: 2067ms
memory: 12880kb
input:
200000 81680 76838 613888876 587957914 198979157 822070409 771572414 956423522 735630675 195386090 413072573 370775671 366821201 759103355 887069240 425791562 480198984 964392370 571045139 69918434 105403235 130585891 929161775 173193325 587989225 533471222 699981718 847802923 586442939 180332329 61...
output:
960936852
result:
ok 1 number(s): "960936852"
Test #11:
score: 0
Accepted
time: 1755ms
memory: 12548kb
input:
200000 91220 105205 669606004 726732973 405615679 508461591 318840594 861409998 284631403 936958719 947250328 347040871 121416461 99394333 909156607 370576415 378572464 877013117 152690261 992392798 908066995 281718650 822652735 474896480 407144540 554646021 805052591 301197617 583099837 1953227 277...
output:
10165030223607
result:
ok 1 number(s): "10165030223607"
Test #12:
score: 0
Accepted
time: 1585ms
memory: 12184kb
input:
200000 127232 120467 895980455 492723394 67974256 451968973 76401255 93977911 241791237 47804708 449338922 918134740 663986817 479932840 38924404 319676905 350139438 427462753 171072159 971709621 283613979 507344968 142793571 933555229 899830335 24231006 846677144 441919608 211146097 783125953 34819...
output:
915538143
result:
ok 1 number(s): "915538143"
Test #13:
score: 0
Accepted
time: 1508ms
memory: 13176kb
input:
200000 143295 141614 955791474 268985895 276555321 556167768 537607093 476166006 132948564 971746533 785402476 871110069 838805339 820188359 777901312 795957142 37915179 710693261 353090372 95835377 270446384 383039611 224736705 6220228 322677117 670856025 250928705 582340637 484301279 806539754 243...
output:
972259005
result:
ok 1 number(s): "972259005"
Test #14:
score: 0
Accepted
time: 1416ms
memory: 12836kb
input:
200000 157096 159904 974133295 340215689 706474749 323930074 662376441 153321391 950476963 895688357 752869810 192681616 350060349 824007389 811845511 345866305 725690921 698956476 535108586 146332206 257278790 668799672 380308767 373852519 819152827 612448335 655180267 764230864 757456461 829953554...
output:
957299769272
result:
ok 1 number(s): "957299769272"
Test #15:
score: 0
Accepted
time: 1140ms
memory: 12184kb
input:
200000 173159 181051 697507824 116478190 210023105 796725089 123582278 240542194 841634289 819630181 88933363 440624237 156282651 532859126 182226199 527179250 413466662 982186983 717126799 565425255 317740123 618123243 830848122 110081029 241999609 185444425 354399120 536055673 325578934 853367355 ...
output:
920924024876
result:
ok 1 number(s): "920924024876"
Test #16:
score: 0
Accepted
time: 1577ms
memory: 13280kb
input:
200000 21000 56984 200 0 412 269 490 216 698 107 517 563 752 856 874 326 317 906 787 1000 686 304 79 362 367 216 923 629 973 921 717 862 73 40 167 932 80 1000 726 719 6 590 989 569 626 228 250 102 723 604 841 104 677 61 207 363 651 864 164 578 41 243 124 531 473 693 178 523 574 113 609 756 178 548 8...
output:
953
result:
ok 1 number(s): "953"
Test #17:
score: 0
Accepted
time: 1545ms
memory: 13156kb
input:
200000 73811 67576 234 0 489 428 292 104 151 966 629 804 330 833 676 344 967 452 709 70 15 554 525 25 423 81 374 673 685 386 798 684 143 625 221 222 128 458 228 53 980 573 630 197 70 442 464 42 168 195 311 118 424 960 217 303 9 411 240 462 83 721 125 732 137 353 457 661 382 726 592 950 729 157 198 8...
output:
712
result:
ok 1 number(s): "712"
Test #18:
score: 0
Accepted
time: 1260ms
memory: 12272kb
input:
200000 116970 130451 568 0 936 383 838 631 237 772 409 908 720 154 8 451 362 21 610 814 98 141 135 652 491 286 847 310 133 348 684 165 162 973 54 82 984 816 686 19 285 496 175 585 945 714 158 307 785 127 257 720 953 718 428 742 256 90 813 343 697 381 468 549 367 692 804 339 246 180 324 63 742 730 64...
output:
786
result:
ok 1 number(s): "786"
Test #19:
score: 0
Accepted
time: 1156ms
memory: 11528kb
input:
200000 153847 163037 146 0 823 568 227 323 377 340 773 912 465 432 771 376 244 825 618 375 733 308 325 215 426 621 173 596 405 542 85 12 477 943 977 698 621 147 864 691 286 890 709 457 448 854 453 468 598 156 166 676 235 431 750 19 398 614 52 9 918 165 370 643 44 319 228 198 341 250 982 922 727 541 ...
output:
351
result:
ok 1 number(s): "351"
Test #20:
score: 0
Accepted
time: 2051ms
memory: 13280kb
input:
200000 34646 46921 1376 0 3625 3613 715 2211 6864 5298 8737 8133 4362 4024 4323 3263 3079 9770 8434 8894 3444 8864 9573 3035 6014 2563 3251 3344 3413 4903 1805 6013 3396 915 5797 3715 6037 3486 9777 7865 79 8790 8695 1105 9695 6055 571 1276 3145 8874 4318 6771 9329 7746 5239 2765 4296 8940 3120 834 ...
output:
8587
result:
ok 1 number(s): "8587"
Test #21:
score: 0
Accepted
time: 1907ms
memory: 12928kb
input:
200000 65314 84709 1695 0 4535 4712 2755 4999 6700 3104 190 9077 9431 1977 156 6255 1543 1715 453 4478 5291 8711 593 8261 6350 8081 4294 7816 9016 8341 3687 5718 6953 9071 9696 9309 1516 8625 7605 5268 9632 8440 8169 697 8840 1753 1947 5839 3527 9845 6075 7816 1696 3060 974 7482 7456 8054 769 3400 3...
output:
7463
result:
ok 1 number(s): "7463"
Test #22:
score: 0
Accepted
time: 1732ms
memory: 12428kb
input:
200000 105963 120144 3879 0 1653 4286 2868 9802 1536 6698 1463 5352 839 6503 6437 8060 2934 7885 7146 7773 3149 6721 6463 2585 9811 399 248 8858 5575 794 9542 5360 8573 4866 739 6641 6932 2102 9264 2960 5715 9330 3285 4068 1116 4174 9191 4476 6448 7228 8779 8066 1359 8552 5707 4769 1048 1205 6333 47...
output:
7035
result:
ok 1 number(s): "7035"
Test #23:
score: 0
Accepted
time: 1551ms
memory: 11456kb
input:
200000 140699 165864 5845 0 8875 1581 9783 7410 4826 6947 2094 7769 6181 2481 9583 4979 5067 4713 1044 1570 3103 8993 483 2457 2136 289 8172 5870 529 8760 767 6366 7991 4011 5712 3086 3456 9710 8540 9027 8162 5370 4728 2201 7493 7303 5401 1095 2704 2561 5888 2662 5945 25 6874 7879 5542 4738 1005 90 ...
output:
7829
result:
ok 1 number(s): "7829"
Test #24:
score: 0
Accepted
time: 2825ms
memory: 13864kb
input:
200000 24184 22744 4290 0 5434 87501 86904 75409 46283 5856 40758 80493 93612 40292 12034 83275 39476 74881 19631 74468 64457 89881 49937 51624 4806 52068 94084 42839 49969 23388 92317 92905 79624 32321 38928 83025 99178 50822 39127 77459 14351 8500 88082 34628 92125 42073 39204 44557 51148 92079 36...
output:
88463
result:
ok 1 number(s): "88463"
Test #25:
score: 0
Accepted
time: 2465ms
memory: 13188kb
input:
200000 61972 64815 36888 0 56144 26214 79295 70582 15881 1243 97642 68505 41128 5741 7991 77890 18201 86433 98009 48472 949 77410 36488 98775 92496 43037 26303 66252 75395 55109 8099 45878 87425 89074 94698 83763 43285 93332 42652 18445 18010 42513 22776 66779 46077 99334 50998 39220 57435 70669 628...
output:
80927
result:
ok 1 number(s): "80927"
Test #26:
score: 0
Accepted
time: 2238ms
memory: 12492kb
input:
200000 117332 118894 35413 0 84677 62103 92687 45314 80946 96852 65153 34830 65357 28614 49780 16211 99554 14515 59130 91882 73944 62340 35914 45769 88451 83121 99023 70676 75596 896 301 57361 38393 58222 705 12775 10665 66580 58508 22195 79045 40128 54207 19604 22429 22798 35277 6584 55412 2385 298...
output:
62327
result:
ok 1 number(s): "62327"
Test #27:
score: 0
Accepted
time: 1872ms
memory: 12628kb
input:
200000 163051 177822 1801 0 1937 9005 59335 52231 21474 66401 55223 35221 19535 10162 3242 64910 59647 27869 6826 2914 64579 88943 64742 96059 48727 20714 40830 24281 88237 93172 79643 38294 22068 17079 62276 90382 43404 59691 12523 96811 17950 63317 64376 15043 85049 23795 72658 32097 24855 64672 2...
output:
19986
result:
ok 1 number(s): "19986"
Test #28:
score: -100
Time Limit Exceeded
input:
200000 33041 33508 66709 0 185584 623495 697398 422714 297463 461353 759852 815887 859854 869332 490187 751575 384230 408607 868885 760306 174374 123674 976999 73253 406801 372576 704318 479628 908582 960304 190305 412173 275646 817727 632027 569599 416721 674809 326136 244417 319890 38759 125020 15...
output:
847882