QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#388465#8548. China Convex Polygon Contestucup-team112#AC ✓94ms19832kbC++2314.2kb2024-04-13 15:59:342024-04-13 15:59:34

Judging History

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

  • [2024-04-13 15:59:34]
  • 评测
  • 测评结果:AC
  • 用时:94ms
  • 内存:19832kb
  • [2024-04-13 15:59:34]
  • 提交

answer

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #define INTERACTIVE

namespace templates {
// type
using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pil = pair<int, ll>;
using Pli = pair<ll, int>;
using Pll = pair<ll, ll>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using qp = priority_queue<T, vector<T>, greater<T>>;
// clang-format off
#define vec(T, A, ...) vector<T> A(__VA_ARGS__);
#define vvec(T, A, h, ...) vector<vector<T>> A(h, vector<T>(__VA_ARGS__));
#define vvvec(T, A, h1, h2, ...) vector<vector<vector<T>>> A(h1, vector<vector<T>>(h2, vector<T>(__VA_ARGS__)));
// clang-format on

// for loop
#define fori1(a) for (ll _ = 0; _ < (a); _++)
#define fori2(i, a) for (ll i = 0; i < (a); i++)
#define fori3(i, a, b) for (ll i = (a); i < (b); i++)
#define fori4(i, a, b, c) for (ll i = (a); ((c) > 0 || i > (b)) && ((c) < 0 || i < (b)); i += (c))
#define overload4(a, b, c, d, e, ...) e
#define fori(...) overload4(__VA_ARGS__, fori4, fori3, fori2, fori1)(__VA_ARGS__)

// declare and input
// clang-format off
#define INT(...) int __VA_ARGS__; inp(__VA_ARGS__);
#define LL(...) ll __VA_ARGS__; inp(__VA_ARGS__);
#define STRING(...) string __VA_ARGS__; inp(__VA_ARGS__);
#define CHAR(...) char __VA_ARGS__; inp(__VA_ARGS__);
#define DOUBLE(...) double __VA_ARGS__; STRING(str___); __VA_ARGS__ = stod(str___);
#define VEC(T, A, n) vector<T> A(n); inp(A);
#define VVEC(T, A, n, m) vector<vector<T>> A(n, vector<T>(m)); inp(A);
// clang-format on

// const value
const ll MOD1   = 1000000007;
const ll MOD9   = 998244353;
const double PI = acos(-1);

// other macro
#if !defined(RIN__LOCAL) && !defined(INTERACTIVE)
#define endl "\n"
#endif
#define spa ' '
#define len(A) ll(A.size())
#define all(A) begin(A), end(A)

// function
vector<char> stoc(string &S) {
    int n = S.size();
    vector<char> ret(n);
    for (int i = 0; i < n; i++) ret[i] = S[i];
    return ret;
}
string ctos(vector<char> &S) {
    int n      = S.size();
    string ret = "";
    for (int i = 0; i < n; i++) ret += S[i];
    return ret;
}

template <class T>
auto min(const T &a) {
    return *min_element(all(a));
}
template <class T>
auto max(const T &a) {
    return *max_element(all(a));
}
template <class T, class S>
auto clamp(T &a, const S &l, const S &r) {
    return (a > r ? r : a < l ? l : a);
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chclamp(T &a, const S &l, const S &r) {
    auto b = clamp(a, l, r);
    return (a != b ? a = b, 1 : 0);
}

template <typename T>
T sum(vector<T> &A) {
    T tot = 0;
    for (auto a : A) tot += a;
    return tot;
}

template <typename T>
vector<T> compression(vector<T> X) {
    sort(all(X));
    X.erase(unique(all(X)), X.end());
    return X;
}

// input and output
namespace io {
// __int128_t
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
    std::ostream::sentry s(dest);
    if (s) {
        __uint128_t tmp = value < 0 ? -value : value;
        char buffer[128];
        char *d = std::end(buffer);
        do {
            --d;
            *d = "0123456789"[tmp % 10];
            tmp /= 10;
        } while (tmp != 0);
        if (value < 0) {
            --d;
            *d = '-';
        }
        int len = std::end(buffer) - d;
        if (dest.rdbuf()->sputn(d, len) != len) {
            dest.setstate(std::ios_base::badbit);
        }
    }
    return dest;
}

// vector<T>
template <typename T>
istream &operator>>(istream &is, vector<T> &A) {
    for (auto &a : A) is >> a;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        os << A[i];
        if (i != A.size() - 1) os << ' ';
    }
    return os;
}

// vector<vector<T>>
template <typename T>
istream &operator>>(istream &is, vector<vector<T>> &A) {
    for (auto &a : A) is >> a;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<vector<T>> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        os << A[i];
        if (i != A.size() - 1) os << endl;
    }
    return os;
}

// pair<S, T>
template <typename S, typename T>
istream &operator>>(istream &is, pair<S, T> &A) {
    is >> A.first >> A.second;
    return is;
}
template <typename S, typename T>
ostream &operator<<(ostream &os, pair<S, T> &A) {
    os << A.first << ' ' << A.second;
    return os;
}

// vector<pair<S, T>>
template <typename S, typename T>
istream &operator>>(istream &is, vector<pair<S, T>> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        is >> A[i];
    }
    return is;
}
template <typename S, typename T>
ostream &operator<<(ostream &os, vector<pair<S, T>> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        os << A[i];
        if (i != A.size() - 1) os << endl;
    }
    return os;
}

// tuple
template <typename T, size_t N>
struct TuplePrint {
    static ostream &print(ostream &os, const T &t) {
        TuplePrint<T, N - 1>::print(os, t);
        os << ' ' << get<N - 1>(t);
        return os;
    }
};
template <typename T>
struct TuplePrint<T, 1> {
    static ostream &print(ostream &os, const T &t) {
        os << get<0>(t);
        return os;
    }
};
template <typename... Args>
ostream &operator<<(ostream &os, const tuple<Args...> &t) {
    TuplePrint<decltype(t), sizeof...(Args)>::print(os, t);
    return os;
}

// io functions
void FLUSH() {
    cout << flush;
}

void print() {
    cout << endl;
}
template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
    cout << head;
    if (sizeof...(Tail)) cout << spa;
    print(std::forward<Tail>(tail)...);
}

template <typename T, typename S>
void prisep(vector<T> &A, S sep) {
    int n = A.size();
    for (int i = 0; i < n; i++) {
        cout << A[i];
        if (i != n - 1) cout << sep;
    }
    cout << endl;
}
template <typename T, typename S>
void priend(T A, S end) {
    cout << A << end;
}
template <typename T>
void prispa(T A) {
    priend(A, spa);
}
template <typename T, typename S>
bool printif(bool f, T A, S B) {
    if (f)
        print(A);
    else
        print(B);
    return f;
}

template <class... T>
void inp(T &...a) {
    (cin >> ... >> a);
}

} // namespace io
using namespace io;

// read graph
vector<vector<int>> read_edges(int n, int m, bool direct = false, int indexed = 1) {
    vector<vector<int>> edges(n, vector<int>());
    for (int i = 0; i < m; i++) {
        INT(u, v);
        u -= indexed;
        v -= indexed;
        edges[u].push_back(v);
        if (!direct) edges[v].push_back(u);
    }
    return edges;
}
vector<vector<int>> read_tree(int n, int indexed = 1) {
    return read_edges(n, n - 1, false, indexed);
}

template <typename T = long long>
vector<vector<pair<int, T>>> read_wedges(int n, int m, bool direct = false, int indexed = 1) {
    vector<vector<pair<int, T>>> edges(n, vector<pair<int, T>>());
    for (int i = 0; i < m; i++) {
        INT(u, v);
        T w;
        inp(w);
        u -= indexed;
        v -= indexed;
        edges[u].push_back({v, w});
        if (!direct) edges[v].push_back({u, w});
    }
    return edges;
}
template <typename T = long long>
vector<vector<pair<int, T>>> read_wtree(int n, int indexed = 1) {
    return read_wedges<T>(n, n - 1, false, indexed);
}

// yes / no
namespace yesno {

// yes
inline bool yes(bool f = true) {
    cout << (f ? "yes" : "no") << endl;
    return f;
}
inline bool Yes(bool f = true) {
    cout << (f ? "Yes" : "No") << endl;
    return f;
}
inline bool YES(bool f = true) {
    cout << (f ? "YES" : "NO") << endl;
    return f;
}

// no
inline bool no(bool f = true) {
    cout << (!f ? "yes" : "no") << endl;
    return f;
}
inline bool No(bool f = true) {
    cout << (!f ? "Yes" : "No") << endl;
    return f;
}
inline bool NO(bool f = true) {
    cout << (!f ? "YES" : "NO") << endl;
    return f;
}

// possible
inline bool possible(bool f = true) {
    cout << (f ? "possible" : "impossible") << endl;
    return f;
}
inline bool Possible(bool f = true) {
    cout << (f ? "Possible" : "Impossible") << endl;
    return f;
}
inline bool POSSIBLE(bool f = true) {
    cout << (f ? "POSSIBLE" : "IMPOSSIBLE") << endl;
    return f;
}

// impossible
inline bool impossible(bool f = true) {
    cout << (!f ? "possible" : "impossible") << endl;
    return f;
}
inline bool Impossible(bool f = true) {
    cout << (!f ? "Possible" : "Impossible") << endl;
    return f;
}
inline bool IMPOSSIBLE(bool f = true) {
    cout << (!f ? "POSSIBLE" : "IMPOSSIBLE") << endl;
    return f;
}

// Alice Bob
inline bool Alice(bool f = true) {
    cout << (f ? "Alice" : "Bob") << endl;
    return f;
}
inline bool Bob(bool f = true) {
    cout << (f ? "Bob" : "Alice") << endl;
    return f;
}

// Takahashi Aoki
inline bool Takahashi(bool f = true) {
    cout << (f ? "Takahashi" : "Aoki") << endl;
    return f;
}
inline bool Aoki(bool f = true) {
    cout << (f ? "Aoki" : "Takahashi") << endl;
    return f;
}

} // namespace yesno
using namespace yesno;

} // namespace templates
using namespace templates;

template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {
  public:
    explicit lazy_segtree(const std::vector<S> &v) : _n(int(v.size())) {
        size = 1;
        log  = 0;
        while (size < _n) {
            log++;
            size <<= 1;
        }
        d  = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) update(i);
    }
    explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}

    S prod(int l, int r) {
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S get(int x) {
        return prod(x, x + 1);
    }

    S all_prod() {
        return d[1];
    }

    void apply(int l, int r, F f) {
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

  private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;
    void update(int k) {
        d[k] = op(d[2 * k], d[2 * k + 1]);
    }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};
const ll inf = 1LL << 60;

struct S {
    ll idx;
    ll x;
};
S op(S l, S r) {
    return l.x > r.x ? l : r;
}
S e() {
    return S{-1, -inf};
}
using F = ll;
S mapping(F f, S x) {
    return S{x.idx, x.x + f};
}
F composition(F f, F g) {
    return f + g;
}
F id() {
    return 0;
}

void solve() {
    LL(n, m);
    vec(ll, A, n + 1);
    A[0] = 0;
    fori(i, 1, n + 1) inp(A[i]);
    A.push_back(m);
    VEC(ll, B, n);
    sort(all(B));
    fori(i, 1, n) B[i] += B[i - 1];
    while (B.back() > m) B.pop_back();
    vec(S, ini, 2 * n);
    fori(i, 2 * n) ini[i] = {i, 0};
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(ini);
    stack<int> st;
    int ap    = n;
    bool prog = false;
    ll bb     = -1;
    ll ans    = 0;
    vec(ll, add_, 2 * n);
    while (!B.empty()) {
        ll b = B.back();
        B.pop_back();
        while (b <= A[ap]) {
            if (prog) {
                seg.apply(ap, 2 * n, bb - A[ap]);
                st.push(ap);
                add_[ap] = bb - A[ap];
            } else {
                seg.apply(ap, ap + 1, A[ap + 1] - A[ap]);
            }
            ap--;
            prog = false;
        }
        if (prog) {
            auto res = seg.prod(ap, 2 * n);
            ans += bb - b;
            ans += res.x;
            while (!st.empty() and st.top() < res.idx) {
                int idx = st.top();
                st.pop();
                seg.apply(idx, 2 * n, -add_[idx]);
            }
            seg.apply(res.idx, res.idx + 1, -inf);
            bb = b;
            continue;
        }

        auto res = seg.prod(ap, 2 * n);
        ll ma1   = res.x;
        ll ma2   = A[ap + 1] - b;
        if (ma1 >= ma2) {
            ans += ma1;
            while (!st.empty() and st.top() < res.idx) {
                int idx = st.top();
                st.pop();
                seg.apply(idx, 2 * n, -add_[idx]);
            }
            seg.apply(res.idx, res.idx + 1, -inf);
        } else {
            prog = true;
            bb   = b;
            ans += ma2;
        }
    }
    print(ans);
}

int main() {
#ifndef INTERACTIVE
    cin.tie(0)->sync_with_stdio(0);
#endif
    // cout << fixed << setprecision(12);
    int t;
    t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

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

详细

Test #1:

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

input:

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

output:

9
9
7

result:

ok 3 number(s): "9 9 7"

Test #2:

score: 0
Accepted
time: 28ms
memory: 3588kb

input:

10000
9 879847766
125098132 150509852 181700303 196375322 519766842 560891576 609151480 721527163 805167083
99031467 66330518 6283986 21388462 41109537 83628243 116141243 144052767 192448599
8 30
5 12 16 19 20 23 25 27
3 1 1 4 2 8 2 3
8 30
4 10 13 16 17 20 23 27
6 3 1 2 3 4 7 2
7 586479012
37693706 ...

output:

858888761
28
27
548785306
28
875933380
27
803763192
942603170
720683076
536166430
759475944
28
27
28
886112586
27
28
28
727698126
28
27
29
28
28
28
28
27
28
819730903
755946410
28
26
28
792662140
891539003
583799124
817190966
934413263
28
28
865467960
27
27
29
488557236
27
26
618111955
28
27
8328741...

result:

ok 10000 numbers

Test #3:

score: 0
Accepted
time: 28ms
memory: 3668kb

input:

10000
8 921979410
2012452 24917627 294894613 360777223 466409663 571239725 717231773 737720960
44502046 158432459 29280108 46756101 343060886 113805663 122292234 18336789
9 996365984
93547621 418854579 432723524 452103231 472239725 534297866 551979311 643474068 796448288
94769801 184799140 40559247 ...

output:

897061783
958809789
518874667
508026272
25
817915823
563445073
755045438
917466401
26
27
963697076
28
857532778
28
28
28
599907462
733717366
861642961
553806595
802417186
26
29
29
29
26
27
908132071
816055107
862993074
29
28
27
28
882732250
585539614
900924232
28
556635369
29
890134472
29
636599530
...

result:

ok 10000 numbers

Test #4:

score: 0
Accepted
time: 24ms
memory: 3612kb

input:

10000
10 693426682
39824378 170753052 172063351 204664113 232271632 245840174 254784959 390184491 453231487 570861818
59595344 22173087 116391450 143121946 23632190 35151525 70352626 30324904 25656706 163522735
8 745209526
121015828 125758181 231986462 461404045 468707947 717366997 738929033 7446472...

output:

655017612
738487472
27
27
626514952
500700122
849903776
29
28
921304686
28
28
28
511049979
28
964808180
611201804
970483767
27
860011940
29
508674850
932159377
948125850
876572563
27
27
575252625
663694866
28
28
27
29
964824235
29
675855993
706402286
754992051
871698228
662676082
27
27
709260574
28
...

result:

ok 10000 numbers

Test #5:

score: 0
Accepted
time: 24ms
memory: 3664kb

input:

10000
9 842080350
126196899 281629390 459021362 589053377 623175793 685983677 686703503 729586222 758579378
139044583 175581708 4917601 53914562 1222336 149353315 84085936 136084484 1513682
10 722336436
66051155 127735998 212633619 309660895 320820247 433981470 582010812 605111593 662898478 67592938...

output:

840138188
695635705
27
488244927
611314272
28
29
776832666
523082033
510786580
29
665355993
834007553
26
28
28
27
596775460
27
601211316
508521258
27
29
618048411
550827368
28
685403346
28
548465042
28
717225955
27
28
882022106
844126870
677316532
649858373
25
28
27
559237354
27
29
497165741
28
5888...

result:

ok 10000 numbers

Test #6:

score: 0
Accepted
time: 24ms
memory: 3604kb

input:

10000
8 708514163
23962271 40872775 157099307 187103309 187292974 402257538 501178818 704015400
25220820 70022938 15019601 105088431 93501133 257255953 42050187 77267678
7 30
3 7 14 15 18 25 28
2 2 4 2 5 4 8
10 30
1 3 6 10 14 16 18 21 23 29
1 2 1 1 1 4 3 1 9 2
8 30
6 11 15 19 20 21 26 27
1 1 2 5 12 ...

output:

684362227
27
29
27
28
793316719
779926027
705604988
27
27
29
27
762714343
590862983
651453477
27
29
906481542
609791490
655735160
825013581
27
589806786
769457681
559647071
676833126
28
28
565082202
29
29
29
605930903
736724745
496276423
735975647
27
752861191
498615546
696968479
872153866
847512710...

result:

ok 10000 numbers

Test #7:

score: 0
Accepted
time: 25ms
memory: 3636kb

input:

10000
9 30
10 13 17 20 24 26 27 28 29
2 2 2 7 1 2 1 7 1
7 831527343
75686598 280691289 496275248 534534697 652168969 665687389 764253502
41653637 35883907 77174475 169783531 134532994 338354 215483430
8 718484116
100189900 124378121 342235912 403546854 508604060 531760359 621198327 671653286
1603436...

output:

28
817670569
694754999
26
27
812629714
27
553368309
749769223
28
27
869423605
927591951
28
868501917
27
554113115
27
757872877
834811859
28
27
28
29
552439238
735169432
876903178
581459092
28
27
657892555
26
886754984
28
686160103
789538336
981411102
510312850
890648943
770480532
583276901
718986202...

result:

ok 10000 numbers

Test #8:

score: 0
Accepted
time: 28ms
memory: 3644kb

input:

10000
10 30
3 4 6 14 17 18 20 22 25 29
2 6 3 3 5 1 3 1 2 2
10 30
6 11 15 16 19 20 23 26 28 29
1 3 2 4 1 4 2 4 2 5
7 600683054
113738178 144331374 193930552 194822106 386416391 476890041 530562637
128835461 23989891 53437985 88589084 2092213 37690603 190105270
8 853858494
17017766 188244392 228267168...

output:

28
28
597699287
797386235
727159057
565049429
828474455
27
895177696
28
594056778
912193740
27
620191871
852100623
29
28
27
943358883
580553291
26
29
29
642061746
28
874798456
27
541562041
28
29
642682965
27
28
824610759
28
486459828
704550861
483902395
29
28
27
28
618648751
633419081
533827057
28
2...

result:

ok 10000 numbers

Test #9:

score: 0
Accepted
time: 28ms
memory: 3608kb

input:

10000
10 794490958
33950165 102613172 233931653 294328727 365866988 394195990 502295599 533500764 697722342 789065736
117636901 56842505 67344689 12693883 43898025 33184559 25296165 165237670 98913433 85684653
7 583412616
79630060 103778160 178797644 347021280 412084871 412242198 437485086
22767799 ...

output:

760540793
554564585
27
28
956701395
25
29
28
28
27
28
28
28
616705831
26
28
28
28
28
27
27
27
470127478
28
562109534
638390996
937834685
702323118
665789596
734137704
26
28
826636157
645678237
641375059
791320618
769654094
28
27
868850069
836416112
29
29
28
825545237
831096007
29
28
579941952
28
29
...

result:

ok 10000 numbers

Test #10:

score: 0
Accepted
time: 28ms
memory: 3836kb

input:

10000
7 620163263
2210088 111033028 213072508 221754874 270340156 465271372 605401151
6589256 133531932 80578109 1717576 194259279 19940297 73135525
8 821458748
94147403 103911199 119213944 148910116 274334138 396035434 415716320 720330739
17483998 40595682 113502043 152348211 87133614 140810847 126...

output:

617953175
759227323
28
577328355
863285321
667218327
29
28
27
28
815536760
559280576
503382454
27
854334502
533028547
967848554
28
767236520
527447546
27
28
625532436
557267576
964127503
27
941231576
648972067
627806338
27
27
685426661
28
27
500624304
27
896818489
29
29
762801184
27
28
27
28
28
7797...

result:

ok 10000 numbers

Test #11:

score: 0
Accepted
time: 24ms
memory: 3904kb

input:

10000
8 748462261
126938743 298205026 460858560 493696867 561517982 598369982 611594963 660762051
9836010 43420294 113911448 87081999 64171127 65191414 117828249 86952635
9 818975929
111152475 125419210 135487970 248358986 365050068 500993620 620295174 693052429 740583941
4529198 15575283 36039923 1...

output:

725401270
790111236
28
742737637
803407267
947164183
576552794
29
27
28
29
28
28
874730861
27
855768639
26
28
911087029
26
28
27
583592147
28
813229697
26
614462355
28
514365649
28
621277915
27
472160914
860353209
559573286
28
27
728087897
26
726726326
28
29
855714743
880622108
27
28
924203964
27
85...

result:

ok 10000 numbers

Test #12:

score: 0
Accepted
time: 24ms
memory: 3640kb

input:

10000
8 796414787
31461520 50761715 90495707 251124998 341850881 720825960 773620389 780205466
54722380 216907544 23636692 98146858 23139876 206884562 69929854 45979367
8 870995852
157940387 214396482 255563234 292144526 336132163 634226211 655076826 795592633
219513340 91244154 123598065 6795235 13...

output:

762693039
806768710
736355372
26
28
28
729100973
862887449
570384939
28
594631648
676565090
28
913095700
562500308
673390494
28
28
655289472
27
28
28
28
29
888685546
690676876
835447840
632836562
666794814
28
908883242
864921023
643425480
652704139
29
893801977
848367692
681211139
760058749
61436934...

result:

ok 10000 numbers

Test #13:

score: 0
Accepted
time: 83ms
memory: 19356kb

input:

1
93849 788867517
27106 35801 44166 45367 71580 75909 79832 80217 88191 125196 128361 161338 162562 166454 169706 187030 193620 198170 213307 218172 219965 224851 227874 234787 249446 254210 260203 261675 266494 275046 281192 287637 294087 302671 329113 334903 352098 375155 393228 400443 406748 4227...

output:

788867514

result:

ok 1 number(s): "788867514"

Test #14:

score: 0
Accepted
time: 94ms
memory: 19300kb

input:

1
96398 922474561
1901 2788 13435 21334 21715 32835 37906 50378 60713 63368 72102 79312 89180 93296 98588 109931 111175 112094 128772 131828 133586 135397 138806 139916 144874 153088 182296 199243 203880 203963 204287 206706 206814 212347 219070 224608 228339 232690 244468 250015 252724 266841 27237...

output:

922474558

result:

ok 1 number(s): "922474558"

Test #15:

score: 0
Accepted
time: 84ms
memory: 19076kb

input:

1
90089 742727663
1217 6823 13314 18050 24731 28352 42997 49561 55040 61758 70988 83872 92015 94583 130355 130462 134637 140652 144576 145902 148292 155581 155868 166731 177106 194744 209712 231894 232938 236413 240680 241753 243178 243375 250977 269081 271541 276802 298463 305980 312949 318614 3306...

output:

742727661

result:

ok 1 number(s): "742727661"

Test #16:

score: 0
Accepted
time: 89ms
memory: 19072kb

input:

1
91457 958286812
4576 10232 12013 36690 43036 75552 78919 83507 87580 95811 98869 103602 117510 124332 134780 145656 146869 149969 154497 155954 166010 181781 197212 200887 221994 232743 244628 247812 269153 275367 277923 279230 306333 311159 311796 313583 315548 326592 339643 353158 355861 410756 ...

output:

958286810

result:

ok 1 number(s): "958286810"

Test #17:

score: 0
Accepted
time: 87ms
memory: 19376kb

input:

1
96636 946300936
1934 10123 19340 33428 51855 58257 62986 64601 69149 84284 86204 100279 108754 109464 116710 125731 142727 155341 195026 227414 235495 248717 251184 296436 297163 300170 301264 312881 317358 332543 333984 372889 376568 391504 405260 410727 415870 436541 442341 446510 449309 460153 ...

output:

946300933

result:

ok 1 number(s): "946300933"

Test #18:

score: 0
Accepted
time: 87ms
memory: 19284kb

input:

1
94463 828132301
542 7003 17038 17374 25312 35177 36656 45415 56758 61075 63587 69933 80702 85732 88898 90611 92986 102266 119807 130948 144192 144289 168919 177198 180392 184131 198442 198628 208736 209804 223497 224487 233230 250463 252862 253768 276441 281549 292476 304007 304196 307425 311458 3...

output:

828132298

result:

ok 1 number(s): "828132298"

Test #19:

score: 0
Accepted
time: 89ms
memory: 19832kb

input:

1
99386 856358032
9342 9789 15768 18347 29826 32298 37146 38716 40663 47080 58496 77227 80563 86981 87770 88422 93717 108195 109329 123588 131010 146152 148141 151411 154282 167351 176879 200229 200934 204370 207654 211060 213202 231489 235581 243411 245746 247478 255086 256528 272684 294411 307780 ...

output:

856358030

result:

ok 1 number(s): "856358030"

Test #20:

score: 0
Accepted
time: 91ms
memory: 19568kb

input:

1
99942 623445854
982 3331 10251 12748 30485 32159 49296 50512 55319 55687 82035 82574 94924 96836 99176 102414 103630 110474 111946 118759 120206 123390 129224 129298 136940 158783 164951 172817 174836 178804 184460 191101 191325 197909 217538 220281 231269 237586 239146 241407 250407 251311 259801...

output:

623445852

result:

ok 1 number(s): "623445852"

Test #21:

score: 0
Accepted
time: 91ms
memory: 19368kb

input:

1
95819 844006123
11453 12062 15525 20176 21653 41258 47316 60272 66576 93784 112286 119375 124809 132817 133053 135731 153151 154062 157182 157782 164364 169065 172029 173121 183564 192849 212900 213437 216589 224462 226749 235646 263949 272370 274975 274998 276231 281002 291211 311728 313567 31970...

output:

844006121

result:

ok 1 number(s): "844006121"

Test #22:

score: 0
Accepted
time: 84ms
memory: 19324kb

input:

1
93880 546964419
2938 9927 12958 13151 15391 15718 15812 18174 19487 23743 25343 30417 33954 36426 37278 43055 47143 51426 51900 53292 57316 72434 73105 74128 84406 85453 87082 90728 91445 93245 101854 105770 112370 119339 127949 135934 136058 138343 142476 146026 151741 155635 157622 159642 160008...

output:

546964417

result:

ok 1 number(s): "546964417"

Test #23:

score: 0
Accepted
time: 92ms
memory: 19828kb

input:

1
98812 961793551
3616 12679 15790 22833 33885 41959 70817 78699 85656 112851 128769 130690 136491 146925 154819 186242 189811 190091 195553 208681 231515 240489 263384 290850 292743 294292 305578 308416 309301 310271 314676 332338 337413 341230 346650 349548 352528 353891 364497 365545 380945 38191...

output:

961793548

result:

ok 1 number(s): "961793548"

Test #24:

score: 0
Accepted
time: 51ms
memory: 19684kb

input:

1
100000 1000000000
5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 55000 60000 65000 70000 75000 80000 85000 90000 95000 100000 105000 110000 115000 120000 125000 130000 135000 140000 145000 150000 155000 160000 165000 170000 175000 180000 185000 190000 195000 200000 205000 210000 215000...

output:

749990000

result:

ok 1 number(s): "749990000"

Test #25:

score: 0
Accepted
time: 23ms
memory: 3608kb

input:

10000
8 720924919
9465427 67948940 69494408 141211447 229699002 635895220 662717937 682981723
412345110 48719110 720924919 720924919 720924919 720924919 720924919 720924919
7 30
1 7 8 19 21 23 24
2 3 2 5 8 10 30
8 30
1 5 7 10 11 15 24 30
2 3 30 30 30 30 30 30
9 30
2 6 7 14 16 21 23 24 28
3 5 5 2 1 1...

output:

444139414
26
15
28
25
26
23
409111591
105252716
26
263082702
266803498
17
11
10
9
97193415
718104325
216551531
663010924
679526925
1
13
26
759768185
25
446871193
532540252
217123161
19
22
859870981
703430943
464548891
21
662490758
633056709
26
25
12
27
843265256
618172231
870394919
442218334
21
24
6...

result:

ok 10000 numbers

Test #26:

score: 0
Accepted
time: 23ms
memory: 3864kb

input:

10000
10 852439504
8030778 94697149 126616560 196288942 213547889 232174173 320262103 396019314 737101891 766336993
57064676 312356378 19228807 268670689 31945461 38465787 852439504 852439504 852439504 852439504
7 30
1 2 5 9 11 14 27
5 3 3 14 30 30 30
8 620393221
22413042 141613203 143478860 1835261...

output:

716814847
23
409242319
454281560
21
235022073
506308552
309975288
797975338
548662792
415575198
28
794637505
807472244
19
25
869782051
25
11
622062939
501430743
27
448380057
639999485
463106414
10
606924724
782981521
26
477961466
26
952695625
333091278
22
859544924
702599301
19
468195707
329389391
2...

result:

ok 10000 numbers

Test #27:

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

input:

10000
8 30
4 8 10 17 20 21 24 30
18 3 4 4 30 30 30 30
7 637172131
21550835 66529272 141827983 431002383 525759222 541617986 554428893
3957828 315739155 10197023 72104531 48919779 364607 182334718
10 30
1 3 7 8 11 16 21 26 29 30
25 30 30 30 30 30 30 30 30 30
9 30
3 5 16 17 21 23 25 26 27
1 8 13 2 30 ...

output:

17
608137853
3
20
706750621
311748892
28
19
22
446192291
21
8
18
160811280
117553682
276153368
7
22
8
679025323
18
686399606
761478576
559476806
28
6
2
21
726933409
2
25
11
26
706427322
736150007
17
19
531680320
867086855
363402927
532593615
26
40095414
4
28
17
550467192
13
592649091
19
27
19
26
188...

result:

ok 10000 numbers

Test #28:

score: 0
Accepted
time: 23ms
memory: 3872kb

input:

10000
10 525555127
22660876 67007260 106301240 178512608 197830931 243266860 243313266 258872639 465022582 471341779
12533746 49649344 22255856 82743749 19327238 37909573 65108888 62431762 60842729 104906435
10 631177236
82333932 130336765 207925786 247765703 358205020 456517029 502067905 577796920 ...

output:

496770236
396185680
523306582
853807818
25
620565760
22
26
493128763
259558988
9
811267727
7
297293779
973078431
387555027
675338739
27
23
763330069
23
28
259383269
76646841
551176605
9
20
318003762
24
24
349552267
701775190
28
504364890
27
620685649
567776438
180802390
17
19
2
522565982
483453964
4...

result:

ok 10000 numbers

Test #29:

score: 0
Accepted
time: 19ms
memory: 3676kb

input:

10000
8 631495946
10320116 88036613 141985663 217227311 231465454 388813844 530605984 575446189
19506558 54009097 65876927 70516136 79504988 57965180 129176590 134330206
7 645928837
6688071 23257469 298415461 344781389 387454270 459619210 639384034
51182665 200995838 4031816 125874016 645928837 6459...

output:

597751245
573453684
62981416
333185472
23
17
275460832
135082278
575644503
24
18
773295799
22
835782021
9
209693254
18
84634839
27
9
484441051
20
25
90312880
83025500
29
5
921903776
26
399150435
566858540
10
533260638
537191950
13
22
193695439
21
14
385584554
400231309
20
606396301
643582432
27
8454...

result:

ok 10000 numbers

Test #30:

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

input:

10000
10 900025869
10703771 102406696 262042800 273183576 288245684 401909775 425645891 439651291 480612404 689722431
419653197 53597605 35356251 900025869 900025869 900025869 900025869 900025869 900025869 900025869
9 591339581
142556598 144783196 153368171 210823932 231122305 302908777 358415227 52...

output:

579049569
549871639
20
4
742139204
918878716
17
26
870238745
237698632
5
27
5
21
102900306
492364068
20
314211208
888898877
14
457194530
29
162642388
657794379
23
715119216
809554696
100384288
14
27
473695047
17
169308803
17
636420013
886709295
9
581565050
24
607114451
550243654
788169824
10
27
28
4...

result:

ok 10000 numbers

Test #31:

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

input:

10000
7 30
5 6 8 10 17 23 24
6 5 12 4 30 30 30
9 30
1 2 5 8 10 13 15 23 27
1 27 30 30 30 30 30 30 30
10 30
4 5 7 12 16 18 21 22 25 30
1 2 2 1 2 5 11 2 2 2
9 30
5 7 8 16 17 19 21 22 30
22 1 7 30 30 30 30 30 30
7 30
7 8 16 17 18 19 23
2 2 11 7 2 3 30
10 775020935
28412091 49996866 299225828 420894665 ...

output:

19
10
28
16
25
686128914
10
20
603325531
722751652
10
668061045
29
20
20
15
388296521
878473954
338868599
27
259289369
26
632044420
642815532
8
26
445507395
22
9
474288778
25
637551859
10
242467880
688198610
279617576
25
285729037
602795167
28
611782175
520868246
5
162344523
881135015
18
17
42635349...

result:

ok 10000 numbers

Test #32:

score: 0
Accepted
time: 23ms
memory: 3640kb

input:

10000
9 30
3 5 12 14 20 23 24 26 30
3 3 5 6 3 2 4 1 1
7 30
2 8 9 10 11 12 19
1 3 1 9 1 1 13
8 962324940
158538075 316947422 412399052 508116684 669131782 870874179 880214903 910448953
277848957 21966537 76384640 13909969 2752338 419343157 103786222 962324940
10 747409716
41638238 86026694 92725023 9...

output:

28
27
914454961
736918262
264253076
27
6
26
24
4
5
20
747065933
96517011
19
584068932
18
28
347412547
206186516
25
684464397
3
441689152
17
28
431239841
17
11
8
4
759993546
117835609
75776199
15
576033457
23
18
59213463
8
27
8
651968569
21
25
748089764
470090565
280271977
560422149
631444457
2542545...

result:

ok 10000 numbers

Test #33:

score: 0
Accepted
time: 23ms
memory: 3900kb

input:

10000
8 30
2 3 5 11 16 17 21 29
5 13 11 30 30 30 30 30
9 518824150
139129154 148935761 307233207 313641375 324465840 359433951 408463762 481139814 513013298
57764983 219458835 64836763 15644143 42029651 7815225 518824150 518824150 518824150
9 660753785
15867881 50983151 57052895 263529865 282012905 ...

output:

15
478158833
475681772
27
182771914
315387260
21
28
488283847
922078891
27
718288243
1
25
501461541
582519738
12
12
674192106
388614553
25
662861148
680266039
10
377004630
21
14
241692770
25
20
374970632
8
435226985
28
186034041
469186248
531441787
798142857
16
23
27
21
22
606631344
27
621707320
596...

result:

ok 10000 numbers

Test #34:

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

input:

10000
10 30
2 3 7 8 9 15 16 20 27 30
13 30 30 30 30 30 30 30 30 30
7 933728118
189486626 255278235 286567027 669812847 721577939 779122330 841789602
80888658 255234697 67241224 117894521 14359838 107943417 116784692
8 30
1 3 15 20 24 25 29 30
5 5 3 2 9 1 1 4
8 915666642
177619838 217661287 300982552...

output:

7
888079488
29
673153095
574382933
3
859169762
410513007
27
58773552
450402126
21
11
649244396
13
616887633
351986861
19
705661660
721718578
901443528
26
758240918
25
5
9
372116223
299135648
834262541
19
399222385
471631110
28
28
504344401
27
26
23
17
25
18
667336702
16
7
26
18
5
25
192321604
26
26
...

result:

ok 10000 numbers

Test #35:

score: 0
Accepted
time: 23ms
memory: 3668kb

input:

10000
10 30
2 9 11 17 19 20 23 25 27 30
22 1 2 30 30 30 30 30 30 30
7 30
1 11 13 17 19 20 21
10 9 4 30 30 30 30
10 945394895
64236786 166246588 207801481 311231593 325288919 452715036 545260108 651389426 658448727 896563952
136738788 487076849 945394895 945394895 945394895 945394895 945394895 945394...

output:

16
18
365541342
448297527
24
805860707
536834580
143408097
334541880
495494276
663427841
26
20
19
22
11
242052294
295601986
11
21
23
274537793
516565192
277435597
713796207
398092064
28
575166166
428716649
393853730
223779893
26
25
253131922
439176964
263979795
22
247829963
896654010
17
153075857
28...

result:

ok 10000 numbers

Test #36:

score: 0
Accepted
time: 51ms
memory: 19508kb

input:

1
94517 842160426
7997 17525 17885 22398 28674 34647 47099 52537 53426 59089 60469 63314 65463 66566 70312 70551 74164 74477 81182 85902 96146 102899 107890 110732 121756 121791 132223 152172 161199 190279 202477 211477 231150 235521 253503 273346 276007 276840 279878 293753 295273 307261 313404 322...

output:

594721376

result:

ok 1 number(s): "594721376"

Test #37:

score: 0
Accepted
time: 33ms
memory: 19760kb

input:

1
98928 742396981
305 21968 23497 33360 34124 43973 44949 46498 53295 56056 58084 82663 94624 103101 117662 118858 122310 128363 133072 160407 161528 166619 213940 222129 224653 227698 236035 238352 239692 242480 289534 293344 309523 311945 331188 333508 338923 343147 347729 368426 388781 391367 393...

output:

125334053

result:

ok 1 number(s): "125334053"

Test #38:

score: 0
Accepted
time: 53ms
memory: 19360kb

input:

1
94266 603438255
19820 22915 24175 25317 26083 35208 37253 39147 46150 54696 59700 83245 86483 97949 101899 107249 107408 113851 127023 131959 136671 140834 152637 155361 157134 159235 171918 172628 173752 188413 193288 200113 218247 234705 239121 246762 249938 251356 258408 271214 271356 279498 30...

output:

383944560

result:

ok 1 number(s): "383944560"

Test #39:

score: 0
Accepted
time: 42ms
memory: 19708kb

input:

1
98699 629317659
13027 14114 25666 32825 35316 37087 42547 52617 58556 58933 71840 73879 103972 105129 116521 121288 121416 134678 140920 142178 155129 163109 164029 174576 176210 196079 196151 198545 205864 210262 214337 217345 219245 219250 229157 247350 257036 261420 265641 267349 269077 272799 ...

output:

344132848

result:

ok 1 number(s): "344132848"

Test #40:

score: 0
Accepted
time: 39ms
memory: 19392kb

input:

1
96636 946300936
1934 10123 19340 33428 51855 58257 62986 64601 69149 84284 86204 100279 108754 109464 116710 125731 142727 155341 195026 227414 235495 248717 251184 296436 297163 300170 301264 312881 317358 332543 333984 372889 376568 391504 405260 410727 415870 436541 442341 446510 449309 460153 ...

output:

311918114

result:

ok 1 number(s): "311918114"

Test #41:

score: 0
Accepted
time: 75ms
memory: 19748kb

input:

1
97696 579464370
8030 15511 21486 24001 30107 34762 53443 59898 60387 62722 67757 70631 76477 81575 83763 88614 92168 119884 132234 144106 153327 154838 155621 179623 186389 192875 204987 210201 211904 216555 216992 219936 220883 230739 231644 240896 241845 246104 254952 255189 261181 262528 266881...

output:

549602254

result:

ok 1 number(s): "549602254"

Test #42:

score: 0
Accepted
time: 64ms
memory: 19256kb

input:

1
92686 737634633
6319 15460 30331 30895 36248 49722 54264 55401 55968 59110 63434 74760 78538 85258 86904 87541 121413 122456 132640 135898 146288 150010 160173 165175 170005 170584 176752 186758 191745 193505 203042 210889 213740 221030 230311 241208 243684 253381 259417 259801 264884 265572 27176...

output:

648866979

result:

ok 1 number(s): "648866979"

Test #43:

score: 0
Accepted
time: 56ms
memory: 19384kb

input:

1
96436 664778097
4942 7854 19110 29066 39055 50424 51557 55772 58209 66227 66539 74733 90732 91669 102226 106423 110443 115736 121112 126495 127437 129247 131094 132729 134073 154746 162084 163873 165019 175514 176870 187763 190946 194978 231950 237308 239955 254888 254981 260086 261484 263998 2853...

output:

567392110

result:

ok 1 number(s): "567392110"

Test #44:

score: 0
Accepted
time: 38ms
memory: 19432kb

input:

1
95873 851845143
10479 11790 21564 23968 29158 44282 56238 57840 67404 68642 91524 109788 111853 125465 129609 132464 133162 138089 150298 156419 170545 174250 176359 192639 192771 201890 206804 216030 218450 224653 229115 249016 251743 253291 254991 255654 267633 279410 303286 303436 304222 304887...

output:

92755585

result:

ok 1 number(s): "92755585"

Test #45:

score: 0
Accepted
time: 49ms
memory: 19324kb

input:

1
93869 768451236
3446 11644 11945 18193 23768 24581 36355 38576 40047 40235 61127 62532 64175 65440 74656 78401 79941 86183 101593 112196 120209 126021 136276 147914 148420 148538 177028 187025 193349 194054 197291 205779 208653 213278 222597 234582 241977 245720 250684 274332 282942 285740 301003 ...

output:

473709177

result:

ok 1 number(s): "473709177"

Test #46:

score: 0
Accepted
time: 77ms
memory: 19104kb

input:

1
91528 500984411
21352 24754 26888 31923 39233 50086 79257 85736 99255 110065 134760 140931 141849 142314 143998 147202 149899 150989 155622 156494 166121 167313 177112 185066 190595 191102 191472 198655 202762 203252 204886 212948 237644 250529 260595 263018 268152 269306 269542 285671 300026 3001...

output:

497448795

result:

ok 1 number(s): "497448795"

Test #47:

score: 0
Accepted
time: 13ms
memory: 19704kb

input:

1
100000 1000000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 9...

output:

0

result:

ok 1 number(s): "0"

Extra Test:

score: 0
Extra Test Passed