QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#699223#6773. True Storybeamishboys#AC ✓22ms4552kbC++207.6kb2024-11-02 06:33:562024-11-02 06:33:57

Judging History

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

  • [2024-11-02 06:33:57]
  • 评测
  • 测评结果:AC
  • 用时:22ms
  • 内存:4552kb
  • [2024-11-02 06:33:56]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

/* Macros {{{ */
/*  A lot of this is from some of Benq's submissions
    [https://codeforces.com/profile/Benq]
    Ugly af to the eyes, but with vim fold its barable
    Hopefully c++20 concepts can make all this stuff must cleaner */

/* Basics {{{ */
using ll = long long;
using ld = long double;
using str = string;

using pi = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
#define mp make_pair
#define fi first
#define se second

#define arr array
#define ve vector
using vi = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;

using vpi = vector<pi>;
using vpll = vector<pll>;
using vpld = vector<pld>;

using vvi = vector<vi>;
using vvll = vector<vll>;
using vvld = vector<vld>;

using vvpi = vector<vpi>;
using vvpll = vector<vpll>;
using vvpld = vector<vpld>;

#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz size()
#define rsz(a) resize(a)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

#define For(i, a, b) for (int i = a; i < b; ++i)
#define Rof(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define rep(a) For(_, 0, a)
#define each(a, x) for (auto &a : x)
#define reach(a, x) for (auto a = x.rbegin(); a != x.rend(); ++a)

template <typename T, typename U>
inline void cmin(T &x, U y) {
    if (y < x) x = y;
}
template <typename T, typename U>
inline void cmax(T &x, U y) {
    if (x < y) x = y;
}
/*}}}*/

/* IO {{{ */

/* Template Macros {{{ */
#define tcT template <class T
#define tcTU tcT, class U
#define tcTUU tcT, class... U
/*}}}*/

inline namespace Helpers { /*{{{*/
tcT, class = void > struct is_iterable : false_type {};
tcT > struct is_iterable<
          T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>>
    : true_type {};
tcT > constexpr bool is_iterable_v = is_iterable<T>::value;

tcT, class = void > struct is_readable : false_type {};
tcT > struct is_readable<T, typename std::enable_if_t<is_same_v<
                                decltype(cin >> declval<T &>()), istream &>>>
    : true_type {};
tcT > constexpr bool is_readable_v = is_readable<T>::value;

tcT, class = void > struct is_printable : false_type {};
tcT > struct is_printable<T, typename std::enable_if_t<is_same_v<
                                 decltype(cout << declval<T>()), ostream &>>>
    : true_type {};
tcT > constexpr bool is_printable_v = is_printable<T>::value;
} /* namespace Helpers */
/*}}}*/

inline namespace Input { /*{{{*/
tcT > constexpr bool needs_input_v = !is_readable_v<T> && is_iterable_v<T>;
tcTUU > void re(T &t, U &...u);
tcTU > void re(pair<T, U> &p); /* pairs */

/* re: read{{{ */
tcT > typename enable_if<is_readable_v<T>, void>::type re(T &x) {
    cin >> x;
} /* default */
tcT > typename enable_if<needs_input_v<T>, void>::type re(
          T &i);                                   // vectors, arrays, etc...
tcTU > void re(pair<T, U> &p) { re(p.fi, p.se); }  // pairs
tcT > typename enable_if<needs_input_v<T>, void>::type re(T &i) {
    each(x, i) re(x);
}
tcTUU > void re(T &t, U &...u) {
    re(t);
    re(u...);
} /* read multiple}}} */

/* rv: resize and read vectors{{{ */
void rv(size_t) {}
tcTUU > void rv(size_t N, ve<T> &t, U &...u);
template <class... U>
void rv(size_t, size_t N2, U &...u);
tcTUU > void rv(size_t N, ve<T> &t, U &...u) {
    t.rsz(N);
    re(t);
    rv(N, u...);
}
template <class... U>
void rv(size_t, size_t N2, U &...u) {
    rv(N2, u...);
} /*}}}*/

/* dumb shortcuts to read in ints{{{ */
void decrement() {} /* subtract one from each */
tcTUU > void decrement(T &t, U &...u) {
    --t;
    decrement(u...);
}
#define ints(...)    \
    int __VA_ARGS__; \
    re(__VA_ARGS__);
#define int1(...)      \
    ints(__VA_ARGS__); \
    decrement(__VA_ARGS__); /*}}}*/
} /* namespace Input */
/*}}}*/

inline namespace ToString { /*{{{*/
tcT > constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>;

/* ts: string representation to print */
tcT > typename enable_if<is_printable_v<T>, str>::type ts(T v) {
    stringstream ss;
    ss << fixed << setprecision(15) << v;
    return ss.str();
} /* default */
tcT > str bit_vec(T t) { /* bit vector to string */
    str res = "{";
    For(i, 0, t.sz) res += ts(t[i]);
    res += "}";
    return res;
}
str ts(ve<bool> v) { return bit_vec(v); }
template <size_t SZ>
str ts(bitset<SZ> b) {
    return bit_vec(b);
} /* bit vector */
tcTU > str ts(pair<T, U> p); /* pairs */
tcT > typename enable_if<needs_output_v<T>, str>::type ts(
          T v); /* vectors, arrays */
tcTU > str ts(pair<T, U> p) { return "(" + ts(p.fi) + ", " + ts(p.se) + ")"; }
tcT > typename enable_if<is_iterable_v<T>, str>::type ts_sep(T v, str sep) {
    /* convert container to string w/ separator sep */
    bool fst = 1;
    str res = "";
    for (const auto &x : v) {
        if (!fst) res += sep;
        fst = 0;
        res += ts(x);
    }
    return res;
}
tcT > typename enable_if<needs_output_v<T>, str>::type ts(T v) {
    return "{" + ts_sep(v, ", ") + "}";
}

/* for nested DS */
template <int, class T>
typename enable_if<!needs_output_v<T>, ve<str>>::type ts_lev(const T &v) {
    return {ts(v)};
}
template <int lev, class T>
typename enable_if<needs_output_v<T>, ve<str>>::type ts_lev(const T &v) {
    if (lev == 0 || !v.sz) return {ts(v)};
    ve<str> res;
    for (const auto &t : v) {
        if (res.sz) res.back() += ",";
        ve<str> tmp = ts_lev<lev - 1>(t);
        res.insert(end(res), all(tmp));
    }
    For(i, 0, res.sz) {
        str bef = " ";
        if (i == 0) bef = "{";
        res[i] = bef + res[i];
    }
    res.back() += "}";
    return res;
}
} /* namespace ToString */
/*}}}*/

inline namespace Output { /*{{{*/
template <class T>
void pr_sep(ostream &os, str, const T &t) {
    os << ts(t);
}
template <class T, class... U>
void pr_sep(ostream &os, str sep, const T &t, const U &...u) {
    pr_sep(os, sep, t);
    os << sep;
    pr_sep(os, sep, u...);
}
/* print w/ no spaces */
template <class... T>
void pr(const T &...t) {
    pr_sep(cout, "", t...);
}
/* print w/ spaces, end with newline */
void ps() { cout << "\n"; }
template <class... T>
void ps(const T &...t) {
    pr_sep(cout, " ", t...);
    ps();
}
/* debug to cerr */
template <class... T>
void dbg_out(const T &...t) {
    pr_sep(cerr, " | ", t...);
    cerr << endl;
}
void loc_info(int line, str names) {
    cerr << "Line(" << line << ") -> [" << names << "]: ";
}
template <int lev, class T>
void dbgl_out(const T &t) {
    cerr << "\n\n" << ts_sep(ts_lev<lev>(t), "\n") << "\n" << endl;
}
} /* namespace Output */
/*}}}}}}}}}*/

int n, k, x, p0;

vi s, t, p;

void solve() {
    re(n, k, x, p0), rv(n, s), rv(k, t), rv(k, p);

    sort(all(s), greater{});

    int l = 0, r = s.size()-1;

    int mt = p0;
    for(int i=0; i<k; ++i) cmax(mt, p[i] - t[i]);

    auto check = [&](int speed) {
        return ( ll(speed) * ll(mt) >= x );
    };

    if(!check(s[0])) { ps(0); return; }

    while(l < r) {
        int m = (l+r+1)>>1;
        if(check(s[m])) l = m;
        else r = m-1;
    }

    ps(l+1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    /* cout << fixed << setprecision(6); */
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; i++) solve();

    return 0;
    // you should actually read the stuff at the bottom
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 3 10 4
1 5 2 1
3 4 5
7 9 10

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

1 3 10 3
1
2 3 4
5 8 10

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 22ms
memory: 4388kb

input:

100000 100000 544857367 2
45337851 26009328 15109007 11351428 108994261 7849241 17594424 49523907 45417024 54467076 60475979 54550753 30367925 22635509 272520858 49488818 90740887 32100499 21719978 20217697 22756760 32141867 23665455 90791528 30224242 21821163 23727178 13022129 30321908 21859760 341...

output:

100000

result:

ok single line: '100000'

Test #4:

score: 0
Accepted
time: 17ms
memory: 4544kb

input:

100000 100000 952144339 3
55978491 28891209 30764133 73202535 10363511 26399650 73193857 11050595 50138706 35213415 158763870 45394118 29711543 27226014 18347560 47615161 52942830 45283718 45268901 79349900 12634867 21153206 19438268 38106844 52860935 25132415 68017329 33907567 23855866 21625728 433...

output:

100000

result:

ok single line: '100000'

Test #5:

score: 0
Accepted
time: 18ms
memory: 4384kb

input:

100000 100000 861312012 213
2930319 4924031 22699434 5536443 8274332 18738805 6676085 8383208 57465745 4425773 18042887 7619913 3971674 6899778 4032324 14434558 45293265 6527910 11865850 8503737 6801962 9561267 19600731 39190716 10483549 6288014 7777162 14447687 4032050 2209849 10854895 6635250 1167...

output:

99999

result:

ok single line: '99999'

Test #6:

score: 0
Accepted
time: 21ms
memory: 4552kb

input:

100000 100000 929055728 64
4678564 15044741 3494711 3575097 4266330 3198032 6433626 7764960 10267603 8916436 7088568 6440301 13159950 3495613 23916569 4893109 4987058 2422388 4239816 3598905 4737250 4050970 5619806 2682505 6987288 5873825 1793494 4159178 3349941 4304864 3881878 5380690 3385614 55371...

output:

99994

result:

ok single line: '99994'

Test #7:

score: 0
Accepted
time: 17ms
memory: 4404kb

input:

100000 100000 248146442 143
664931 951822 2163295 1868430 562534 993898 752527 503694 511566 893557 1432204 1332028 1524507 1226078 498905 2914975 292984 383719 2636352 745258 2274553 250430 3088734 803160 239231 202105 332018 2001371 290489 175723 694559 1569928 80452 1819911 227867 5418914 1229987...

output:

99899

result:

ok single line: '99899'

Test #8:

score: 0
Accepted
time: 18ms
memory: 4484kb

input:

100000 100000 870780091 795
665678 844523 383484 537539 800020 1098254 488820 1106470 810781 596219 746216 1386783 1450234 656905 946807 610387 401177 1442710 713631 1655233 1115222 789437 413697 744052 4351285 2489215 481224 856662 5523686 551873 1002460 913985 759269 2506784 2740038 3770580 138407...

output:

99903

result:

ok single line: '99903'

Test #9:

score: 0
Accepted
time: 22ms
memory: 4380kb

input:

100000 100000 608323112 1600
341497 499855 1113106 291291 259919 443431 1242086 238567 299962 981292 455056 555461 97752 1404107 133886 471240 1653194 915421 342101 127178 256327 224225 85242 505280 139750 381085 727183 357269 1049595 860775 156501 687894 274332 1277675 564966 237377 1 282154 604649...

output:

99068

result:

ok single line: '99068'

Test #10:

score: 0
Accepted
time: 22ms
memory: 4392kb

input:

100000 100000 617688178 260
2105285 183083 218544 359952 255820 148413 347788 147275 355058 106645 45815 123634 116489 295688 166315 661394 36672 125844 55582 265242 468126 2013564 191935 226217 163891 279615 109365 113560 89952 833155 250529 116296 6985 86613 231733 26747 139480 110408 330349 47431...

output:

95310

result:

ok single line: '95310'

Test #11:

score: 0
Accepted
time: 22ms
memory: 4376kb

input:

100000 100000 851197196 761
217303 23990 183710 95220 32232 134402 140389 5373 214637 1 56358 424129 147715 173344 164259 76784 102786 1 104754 33388 147209 1 148101 31027 104249 175449 360543 115412 156798 241408 47710 1 711111 267501 258463 129222 205007 100341 64906 20002 181604 125166 39081 3352...

output:

87973

result:

ok single line: '87973'

Test #12:

score: 0
Accepted
time: 20ms
memory: 4424kb

input:

100000 100000 446291590 9436
95233 141685 118942 33156 101933 1 1 79786 1 42166 58435 106539 55197 51421 1 1 12642 31480 1 30112 502653 14741 97326 94885 39268 117170 1 280635 54247 127297 1 1 1 99222 177725 1 81779 1 1 48629 75403 1 1 41691 1365270 1 337473 1 1 1 215197 28045 1 11411 425988 1 44188...

output:

66322

result:

ok single line: '66322'

Test #13:

score: 0
Accepted
time: 21ms
memory: 4472kb

input:

100000 100000 726287423 548
137287 1 562 19937 3698668 42660 103484 1 1 73669 143985 17206 1 119502 83482 37334 82323 585760 547215 90690 143633 62954 48476 283630 8435 42557 14460 36242 1 1109471 136699 4930 1 487250 8504 1 22515 43827 106008 82397 92489 142658 102211 495689 111 65926 86495 48888 2...

output:

73686

result:

ok single line: '73686'

Test #14:

score: 0
Accepted
time: 21ms
memory: 4380kb

input:

100000 100000 506515362 2030
137117 30890 96960 118046 1 1 1 1 1 158279 1 3544 100282 56963 64818 56870 111274 1 1 57964 84949 54371 11701 64234 63104 59744 93738 95126 1 89954 113138 1 9517 67863 107914 85956 1 1 73762 135613 67646 1 137010 1 90810 106723 1 1 238947 101612 207649 1 1 42453 112071 3...

output:

68336

result:

ok single line: '68336'