QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#427556#8775. MountainCraftucup-team112#AC ✓393ms35604kbC++2015.8kb2024-06-01 13:47:572024-06-01 13:47:57

Judging History

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

  • [2024-06-01 13:47:57]
  • 评测
  • 测评结果:AC
  • 用时:393ms
  • 内存:35604kb
  • [2024-06-01 13:47:57]
  • 提交

answer

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #define INTERACTIVE

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

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 x;
    ll cnt;
};
S op(S l, S r) {
    if (l.x == r.x)
        return {l.x, l.cnt + r.cnt};
    else if (l.x < r.x)
        return l;
    else
        return r;
}
S e() {
    return {inf, 0};
}
using F = ll;
S mapping(F f, S x) {
    return {f + x.x, x.cnt};
}
F composition(F f, F g) {
    return f + g;
}
F id() {
    return 0;
}

void solve() {
    LL(Q, W);
    vec(ll, L, Q);
    vec(ll, R, Q);
    vec(ll, X, 0);
    X.push_back(0);
    X.push_back(W);
    fori(i, Q) {
        LL(x, y);
        ll l = max(0LL, x - y);
        ll r = min(W, x + y);
        L[i] = x;
        R[i] = y;
        X.push_back(l);
        X.push_back(r);
    }
    X     = compression(X);
    int n = len(X) - 1;
    vec(S, ini, n);
    fori(i, n) {
        ini[i] = {0, X[i + 1] - X[i]};
    }

    lazy_segtree<S, op, e, F, mapping, composition, id> seg(ini);

    set<pair<ll, ll>> se;
    double sqrt_2 = pow(2, 0.5);
    fori(i, Q) {
        ll l_  = max(0LL, L[i] - R[i]);
        ll r_  = min(W, L[i] + R[i]);
        ll l   = lower_bound(all(X), l_) - X.begin();
        ll r   = lower_bound(all(X), r_) - X.begin();
        ll add = se.count({L[i], R[i]}) ? -1 : 1;

        seg.apply(l, r, add);

        if (add == 1) {
            se.insert({L[i], R[i]});
        } else {
            se.erase({L[i], R[i]});
        }

        auto res = seg.all_prod();
        ll d     = (res.x == 0) ? W - res.cnt : W;
        print(d * sqrt_2);
    }
}

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;
}

// // #pragma GCC target("avx2")
// // #pragma GCC optimize("O3")
// // #pragma GCC optimize("unroll-loops")
// // #define INTERACTIVE
//
// #include "kyopro-cpp/template.hpp"
//
// #include "data_structure/lazySegTree.hpp"
// const ll inf = 1LL << 60;
// struct S {
//     ll x;
//     ll cnt;
// };
// S op(S l, S r) {
//     if (l.x == r.x)
//         return {l.x, l.cnt + r.cnt};
//     else if (l.x < r.x)
//         return l;
//     else
//         return r;
// }
// S e() {
//     return {inf, 0};
// }
// using F = ll;
// S mapping(F f, S x) {
//     return {f + x.x, x.cnt};
// }
// F composition(F f, F g) {
//     return f + g;
// }
// F id() {
//     return 0;
// }
//
// void solve() {
//     LL(Q, W);
//     vec(ll, L, Q);
//     vec(ll, R, Q);
//     vec(ll, X, 0);
//     X.push_back(0);
//     X.push_back(W);
//     fori(i, Q) {
//         LL(x, y);
//         ll l = max(0LL, x - y);
//         ll r = min(W, x + y);
//         L[i] = x;
//         R[i] = y;
//         X.push_back(l);
//         X.push_back(r);
//     }
//     X     = compression(X);
//     int n = len(X) - 1;
//     vec(S, ini, n);
//     fori(i, n) {
//         ini[i] = {0, X[i + 1] - X[i]};
//     }
//
//     lazy_segtree<S, op, e, F, mapping, composition, id> seg(ini);
//
//     set<pair<ll, ll>> se;
//     double sqrt_2 = pow(2, 0.5);
//     fori(i, Q) {
//         ll l_  = max(0LL, L[i] - R[i]);
//         ll r_  = min(W, L[i] + R[i]);
//         ll l   = lower_bound(all(X), l_) - X.begin();
//         ll r   = lower_bound(all(X), r_) - X.begin();
//         ll add = se.count({L[i], R[i]}) ? -1 : 1;
//
//         seg.apply(l, r, add);
//
//         if (add == 1) {
//             se.insert({L[i], R[i]});
//         } else {
//             se.erase({L[i], R[i]});
//         }
//
//         auto res = seg.all_prod();
//         ll d     = (res.x == 0) ? W - res.cnt : W;
//         print(d * sqrt_2);
//     }
// }
//
// 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;
// }

詳細信息

Test #1:

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

input:

3 10
3 2
7 3
9 6

output:

5.656854249492
12.727922061358
12.727922061358

result:

ok 3 numbers

Test #2:

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

input:

5 100
31 41
59 26
31 41
59 26
31 41

output:

101.823376490863
120.208152801713
73.539105243401
0.000000000000
101.823376490863

result:

ok 5 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 3988kb

input:

100 10
6 4
2 3
7 6
5 5
3 6
7 5
5 8
10 4
9 8
0 9
9 10
9 3
2 3
10 10
8 4
10 9
0 1
1 7
0 2
3 4
10 3
3 10
7 4
7 5
1 4
0 7
1 9
5 6
8 8
7 4
8 1
3 9
2 1
5 5
2 1
10 9
8 4
0 9
10 7
4 1
9 10
8 6
5 4
1 4
0 9
9 3
4 8
5 10
7 2
8 10
7 10
3 4
2 2
8 5
0 9
5 3
1 4
6 4
0 3
8 1
1 6
3 8
8 4
6 5
10 2
2 2
8 4
6 1
2 4
6 4...

output:

11.313708498985
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623...

result:

ok 100 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 4088kb

input:

1000 100
95 8
54 8
64 96
47 34
77 47
99 91
45 70
8 6
64 84
48 42
53 14
73 66
38 27
6 52
19 75
33 39
6 24
37 80
27 45
96 48
55 95
67 1
23 78
40 4
76 7
77 22
4 47
41 31
60 54
96 37
79 52
63 40
7 92
17 7
74 12
93 16
87 5
67 43
60 29
71 58
52 41
53 84
38 2
46 87
13 54
54 14
16 93
57 7
91 98
31 23
70 3
9...

output:

18.384776310850
41.012193308820
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237...

result:

ok 1000 numbers

Test #5:

score: 0
Accepted
time: 2ms
memory: 4164kb

input:

1000 1000
942 407
513 739
329 437
605 318
847 416
128 543
588 237
903 365
703 556
313 928
621 344
974 444
780 265
993 889
103 427
94 977
897 586
566 326
785 938
224 952
150 441
716 802
729 584
954 347
640 4
91 633
738 970
823 253
158 890
115 734
327 391
554 258
373 67
396 995
788 73
609 703
627 801
...

output:

657.609306503489
1414.213562373095
1414.213562373095
1414.213562373095
1414.213562373095
1414.213562373095
1414.213562373095
1414.213562373095
1414.213562373095
1414.213562373095
1414.213562373095
1414.213562373095
1414.213562373095
1414.213562373095
1414.213562373095
1414.213562373095
1414.21356237...

result:

ok 1000 numbers

Test #6:

score: 0
Accepted
time: 133ms
memory: 12508kb

input:

200000 10
6 4
4 9
7 9
6 2
0 7
6 7
4 8
10 5
7 8
5 4
3 6
5 9
0 9
7 3
8 2
8 6
5 9
5 10
4 9
0 3
10 5
3 9
7 2
2 3
9 7
5 6
1 7
0 4
9 6
4 7
3 8
6 4
2 7
0 6
8 3
6 2
8 10
1 6
0 4
6 1
3 3
5 8
9 7
8 7
1 10
6 2
1 8
8 6
6 1
6 3
0 6
6 1
5 6
1 1
6 4
7 9
3 5
10 6
2 8
6 7
7 3
6 8
8 5
9 7
4 5
6 4
5 10
8 6
8 5
4 6
4 6...

output:

11.313708498985
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623731
14.142135623...

result:

ok 200000 numbers

Test #7:

score: 0
Accepted
time: 166ms
memory: 13528kb

input:

200000 100
96 9
26 82
73 33
12 92
13 77
87 2
23 79
41 91
75 28
6 45
42 81
27 51
7 64
80 90
27 65
77 72
54 60
79 8
10 61
46 15
65 16
75 95
65 4
89 38
42 74
96 63
48 87
39 78
2 59
36 48
36 66
12 75
44 45
80 86
79 99
26 30
29 54
39 44
7 27
99 23
41 76
23 71
76 51
90 76
59 22
45 70
73 98
24 94
70 54
76 ...

output:

18.384776310850
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.421356237310
141.42135623...

result:

ok 200000 numbers

Test #8:

score: 0
Accepted
time: 309ms
memory: 22844kb

input:

200000 10000
8596 2507
1107 4452
8591 3460
3584 2911
8817 9663
1604 2760
6281 8431
5271 4811
2193 1874
5329 3970
2679 8672
8426 8447
117 4849
3471 6286
177 4806
9726 7217
6743 3882
573 4295
5291 7358
1356 6269
7882 8426
8750 985
5365 8276
7420 6372
8234 6329
7723 9014
3369 1097
7140 8329
3475 447
37...

output:

5530.989242441176
13392.602435673210
14142.135623730952
14142.135623730952
14142.135623730952
14142.135623730952
14142.135623730952
14142.135623730952
14142.135623730952
14142.135623730952
14142.135623730952
14142.135623730952
14142.135623730952
14142.135623730952
14142.135623730952
14142.1356237309...

result:

ok 200000 numbers

Test #9:

score: 0
Accepted
time: 393ms
memory: 35604kb

input:

200000 1000000000
979065421 937279323
384811311 879649222
673927841 883688174
47686221 518846247
805783947 475892423
94359891 104324315
116498230 496486640
155617000 261326127
423462080 949904263
758478482 824824842
594993542 173897699
495194886 158960628
409812195 339201236
958417812 891558399
7055...

output:

1355119095.862843990326
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.3...

result:

ok 200000 numbers

Test #10:

score: 0
Accepted
time: 1ms
memory: 4012kb

input:

3 100
82 61
46 1
82 61

output:

111.722871427475
111.722871427475
2.828427124746

result:

ok 3 numbers

Test #11:

score: 0
Accepted
time: 235ms
memory: 28856kb

input:

200000 200005
199999 1
199998 2
199997 3
199996 4
199995 5
199994 6
199993 7
199992 8
199991 9
199990 10
199989 11
199988 12
199987 13
199986 14
199985 15
199984 16
199983 17
199982 18
199981 19
199980 20
199979 21
199978 22
199977 23
199976 24
199975 25
199974 26
199973 27
199972 28
199971 29
19997...

output:

2.828427124746
5.656854249492
8.485281374239
11.313708498985
14.142135623731
16.970562748477
19.798989873223
22.627416997970
25.455844122716
28.284271247462
31.112698372208
33.941125496954
36.769552621700
39.597979746447
42.426406871193
45.254833995939
48.083261120685
50.911688245431
53.740115370178...

result:

ok 200000 numbers

Test #12:

score: 0
Accepted
time: 228ms
memory: 29044kb

input:

200000 200005
0 200000
1 199999
2 199998
3 199997
4 199996
5 199995
6 199994
7 199993
8 199992
9 199991
10 199990
11 199989
12 199988
13 199987
14 199986
15 199985
16 199984
17 199983
18 199982
19 199981
20 199980
21 199979
22 199978
23 199977
24 199976
25 199975
26 199974
27 199973
28 199972
29 199...

output:

282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
...

result:

ok 200000 numbers

Test #13:

score: 0
Accepted
time: 299ms
memory: 28860kb

input:

200000 200005
188054 11946
25503 174497
5164 194836
199742 258
65650 134350
93448 106552
165510 34490
33001 166999
54081 145919
123066 76934
50244 149756
46561 153439
66523 133477
8593 191407
173633 26367
105494 94506
198495 1505
75564 124436
83182 116818
123337 76663
186899 13101
110487 89513
10858...

output:

33788.390432217988
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
282842.712474619038
2...

result:

ok 200000 numbers

Test #14:

score: 0
Accepted
time: 229ms
memory: 28920kb

input:

200000 200005
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
50 50
51 5...

output:

2.828427124746
5.656854249492
8.485281374239
11.313708498985
14.142135623731
16.970562748477
19.798989873223
22.627416997970
25.455844122716
28.284271247462
31.112698372208
33.941125496954
36.769552621700
39.597979746447
42.426406871193
45.254833995939
48.083261120685
50.911688245431
53.740115370178...

result:

ok 200000 numbers

Test #15:

score: 0
Accepted
time: 227ms
memory: 28884kb

input:

200000 200005
200000 200000
199999 199999
199998 199998
199997 199997
199996 199996
199995 199995
199994 199994
199993 199993
199992 199992
199991 199991
199990 199990
199989 199989
199988 199988
199987 199987
199986 199986
199985 199985
199984 199984
199983 199983
199982 199982
199981 199981
199980...

output:

282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
...

result:

ok 200000 numbers

Test #16:

score: 0
Accepted
time: 302ms
memory: 28876kb

input:

200000 200005
99686 99686
193692 193692
142065 142065
56279 56279
120521 120521
147618 147618
148660 148660
1328 1328
69007 69007
5297 5297
136306 136306
136195 136195
101372 101372
66966 66966
110843 110843
170697 170697
23097 23097
146157 146157
118098 118098
11530 11530
42300 42300
74535 74535
17...

output:

281954.586357448716
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
282849.783542430901
...

result:

ok 200000 numbers

Test #17:

score: 0
Accepted
time: 99ms
memory: 12796kb

input:

200000 1000000000
227478108 704821317
227478108 704821317
227478108 704821317
227478108 704821317
227478108 704821317
227478108 704821317
227478108 704821317
227478108 704821317
227478108 704821317
227478108 704821317
227478108 704821317
227478108 704821317
227478108 704821317
227478108 704821317
22...

output:

1318470491.027638196945
0.000000000000
1318470491.027638196945
0.000000000000
1318470491.027638196945
0.000000000000
1318470491.027638196945
0.000000000000
1318470491.027638196945
0.000000000000
1318470491.027638196945
0.000000000000
1318470491.027638196945
0.000000000000
1318470491.027638196945
0.0...

result:

ok 200000 numbers

Test #18:

score: 0
Accepted
time: 149ms
memory: 12816kb

input:

200000 1000000000
517510913 200230004
39507125 601409920
30526823 972694998
176712 534697072
789676092 648567171
967127462 822743807
176712 534697072
176712 534697072
117560602 867751869
967127462 822743807
227002346 310628813
789676092 648567171
800983841 618498638
39507125 601409920
517510913 2002...

output:

566335974.501638174057
1015038939.091501951218
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.37...

result:

ok 200000 numbers

Test #19:

score: 0
Accepted
time: 179ms
memory: 13124kb

input:

200000 1000000000
351451808 649636951
49985291 500589827
661773922 164694264
186065541 226295124
497991267 744030929
574182692 439989249
853617452 979655888
308109763 216029731
66584658 40643821
855305206 820425533
740812379 441059394
151159173 495945962
214589103 777995590
957581330 407536966
88513...

output:

1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.373095035553
1414213562.3...

result:

ok 200000 numbers

Test #20:

score: 0
Accepted
time: 113ms
memory: 13460kb

input:

200000 1000000000
821475126 617812186
464369722 134670005
821475126 617812186
464369722 134670005
464369722 134670005
821475126 617812186
464369722 134670005
464369722 134670005
464369722 134670005
464369722 134670005
821475126 617812186
464369722 134670005
464369722 134670005
464369722 134670005
46...

output:

1126190670.472317218781
1126190670.472317218781
380904295.031705081463
0.000000000000
380904295.031705081463
1126190670.472317218781
1126190670.472317218781
1126190670.472317218781
1126190670.472317218781
1126190670.472317218781
380904295.031705081463
0.000000000000
380904295.031705081463
0.00000000...

result:

ok 200000 numbers

Test #21:

score: 0
Accepted
time: 138ms
memory: 12632kb

input:

200000 11
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
8 1
10 10
3 1
1 2
9 10
1 4
5 1
1 5
1 6
7 7
2 1
4 1
5 3
7 9
6 4
3 7
6 1
1 8
2 5
2 9
10 9
6 10
9 8
1 2
7 3
6 6
6 6
7 5
1 9
7 9
3 5
9 5
3 3
6 8
10 9
7 5
5 1
2 1
3 2
5 5
8 1
4 9
9 8
1 3
4 8
8 9
2 10
1 4
7 3
4 1
1 2
1 2
5 1
5 4
1 3
2 1
6 2
6 8
5 9
10 7
5...

output:

2.828427124746
4.242640687119
5.656854249492
7.071067811865
8.485281374239
9.899494936612
11.313708498985
12.727922061358
14.142135623731
15.556349186104
15.556349186104
15.556349186104
15.556349186104
15.556349186104
15.556349186104
15.556349186104
15.556349186104
15.556349186104
15.556349186104
15...

result:

ok 200000 numbers

Test #22:

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

input:

200000 4
1 1
2 1
3 1
1 1
3 2
3 3
2 1
3 3
2 1
2 2
2 2
3 1
2 2
3 3
1 2
2 3
1 2
2 1
2 2
1 2
3 1
2 2
2 1
2 1
3 3
2 2
1 2
1 3
2 1
3 3
2 3
3 1
2 1
1 2
1 3
3 1
2 3
2 1
1 2
3 3
1 3
3 3
2 3
2 3
2 1
3 1
3 3
1 2
2 1
2 1
1 1
1 3
1 1
1 1
2 3
2 2
1 2
1 1
1 3
1 1
1 2
1 1
2 3
1 1
2 2
2 2
2 1
2 1
3 2
1 1
3 1
1 2
1 1...

output:

2.828427124746
4.242640687119
5.656854249492
4.242640687119
4.242640687119
5.656854249492
5.656854249492
4.242640687119
4.242640687119
5.656854249492
4.242640687119
4.242640687119
5.656854249492
5.656854249492
5.656854249492
5.656854249492
5.656854249492
5.656854249492
5.656854249492
5.656854249492
...

result:

ok 200000 numbers

Test #23:

score: 0
Accepted
time: 173ms
memory: 12584kb

input:

200000 51
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 1
15 1
16 1
17 1
18 1
19 1
20 1
21 1
22 1
23 1
24 1
25 1
26 1
27 1
28 1
29 1
30 1
31 1
32 1
33 1
34 1
35 1
36 1
37 1
38 1
39 1
40 1
41 1
42 1
43 1
44 1
45 1
46 1
47 1
48 1
49 1
50 1
2 47
25 41
44 8
35 38
37 24
42 32
40 48
19 4
26 4...

output:

2.828427124746
4.242640687119
5.656854249492
7.071067811865
8.485281374239
9.899494936612
11.313708498985
12.727922061358
14.142135623731
15.556349186104
16.970562748477
18.384776310850
19.798989873223
21.213203435596
22.627416997970
24.041630560343
25.455844122716
26.870057685089
28.284271247462
29...

result:

ok 200000 numbers