oj.uz

Submission #660567

# Submission time Handle Problem Language Result Execution time Memory
660567 2022-11-22T11:04:52 Z SorahISA Joker (BOI20_joker) C++17
100 / 100
 792 ms 66220 KB 
#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define double long double
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;

// #define X first
// #define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

template <size_t D, typename T> struct Vec : vector<Vec<D-1, T>> {
    static_assert(D >= 1, "Vector dimension must be greater than zero!");
    template <typename... Args> Vec(int n = 0, Args... args) : vector<Vec<D-1, T>>(n, Vec<D-1, T>(args...)) {}
};

template <typename T> struct Vec<1, T> : vector<T> {
    Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {}
};

#ifdef local
#define fastIO() void()
#define debug(...) \
    _color.eb("\u001b[31m"), \
    fprintf(stderr, "%sAt [%s], line %d: (%s) = ", _color.back().c_str(), __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), _color.pop_back(), \
    fprintf(stderr, "%s", _color.back().c_str())
deque<string> _color{"\u001b[0m"};

template <typename T> concept is_string = is_same_v<T, string&> or is_same_v<T, const string&>;
template <typename T> concept is_iterable = requires (T _t) {begin(_t);};

template <typename T> inline void _print_err(T &&_t);
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>);
template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &);
template <size_t I = 0, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(const tuple<U...> &_t);
template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &);
template <size_t I = 0, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(tuple<U...> &_t);
template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu);

inline void _do() {cerr << "\n";};
template <typename T> inline void _do(T &&_t) {_print_err(_t), cerr << "\n";}
template <typename T, typename ...U> inline void _do(T &&_t, U &&..._u) {_print_err(_t), cerr << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

inline int getRand(int L, int R) {
    if (L > R) swap(L, R);
    return (int)(rng() % ((uint64_t)R - L + 1) + L);
}

template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

struct DSU {
    
    vector<int> p, sz;
    stack<array<int, 4>> stk;
    
    int R(int x) {return x ^ p[x] ? R(p[x]) : x;}
    
    int U(int x, int y) {
        x = R(x), y = R(y);
        if (sz[x] > sz[y]) swap(x, y);
        stk.ee(array{x, p[x], y, sz[y]});
        if (x != y) return sz[y] += sz[x], p[x] = y, 1;
        return 0;
    }
    
    void undo() {
        auto op = stk.top(); stk.pop();
        p[op[0]] = op[1], sz[op[2]] = op[3];
    }
    
    void init(int n) {
        p.resize(n), iota(ALL(p), 0);
        sz.assign(n, 1);
    }
    
} dsu;

deque<array<int, 3>> stk;

void enqueue(int x, int y) {
    // debug("enqueue"s, x, y);
    static int id = 0;
    dsu.U(x, y);
    stk.eb(array{id++, x, y});
}

void dequeue() {
    static int tok = -1;
    
    if (stk.back()[0] <= tok) {
        // debug("dequeue"s, "simple"s);
        dsu.undo(), stk.pb();
        return;
    }
    
    deque<array<int, 3>> op_old, op_new;
    do {
        auto op = stk.back(); dsu.undo(), stk.pb();
        if (op[0] <= tok) op_old.ef(op);
        else              op_new.ef(op);
        if (op[0] == tok) break;
    } while (SZ(stk) and SZ(op_old) < SZ(op_new));
    
    if (!SZ(op_old)) {
        // debug("dequeue"s, "reverse new"s);
        op_new.pf();
        tok = op_new.back()[0];
        while (SZ(op_new)) {
            auto op = op_new.back(); op_new.pb();
            dsu.U(op[1], op[2]), stk.eb(op);
        }
    }
    else {
        // debug("dequeue"s, "pop"s);
        op_old.pb();
        for (auto op : op_new) dsu.U(op[1], op[2]), stk.eb(op);
        for (auto op : op_old) dsu.U(op[1], op[2]), stk.eb(op);
    }
    
    decltype(op_old)().swap(op_old);
    decltype(op_new)().swap(op_new);
}

void solve() {
    int N, M, Q; cin >> N >> M >> Q;
    
    dsu.init(2*N);
    vector<pii> edges(M);
    for (auto &[u, v] : edges) cin >> u >> v, --u, --v;
    for (int i = 0; i < M; ++i) edges.eb(edges[i]);
    
    vector<int> ans(2*M, -1);
    for (int L = 0, R = 0; R < 2*M; ++R) {
        enqueue(2 * edges[R].first, 2 * edges[R].second + 1);
        enqueue(2 * edges[R].first + 1, 2 * edges[R].second);
        while (dsu.R(2 * edges[R].first) == dsu.R(2 * edges[R].first + 1)) {
            // debug("pop"s, L, R);
            dequeue(), dequeue(), ++L;
            // debug(stk);
        }
        ans[R] = L;
        // debug("\n"s, stk);
    }
    
    // debug(ans);
    
    for (int i = 0, L, R; i < Q; ++i) {
        cin >> L >> R, --L, --R;
        if (R >= ans[L+M-1] - 1) cout << "NO" << "\n";
        else                     cout << "YES" << "\n";
    }
}

int32_t main() {
    fastIO();
    
    int t = 1; // cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        // cout << "Case #" << _ << ": ";
        solve();
    }
    
    return 0;
}

/// below are Fast I/O and _print_err templates ///

/*
/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///

#include <unistd.h>

const int S = 65536;

int OP = 0;
char OB[S];

inline char RC() {
    static char buf[S], *p = buf, *q = buf;
    return p == q and (q = (p = buf) + read(0, buf, S)) == buf ? -1 : *p++;
}

inline int RI() {
    static char c;
    int a;
    while (((c = RC()) < '0' or c > '9') and c != '-' and c != -1);
    if (c == '-') {
        a = 0;
        while ((c = RC()) >= '0' and c <= '9') a *= 10, a -= c ^ '0';
    }
    else {
        a = c ^ '0';
        while ((c = RC()) >= '0' and c <= '9') a *= 10, a += c ^ '0';
    }
    return a;
}

inline void WI(int n, char c = '\n') {
    static char buf[20], p;
    if (n == 0) OB[OP++] = '0';
    p = 0;
    if (n < 0) {
        OB[OP++] = '-';
        while (n) buf[p++] = '0' - (n % 10), n /= 10;
    }
    else {
        while (n) buf[p++] = '0' + (n % 10), n /= 10;
    }
    for (--p; p >= 0; --p) OB[OP++] = buf[p];
    OB[OP++] = c;
    if (OP > S-20) write(1, OB, OP), OP = 0;
}

/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
*/

#ifdef local

template <typename T> inline void _print_err(T &&_t) {cerr << _t;}

template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>) {
    string _tmp_color = _color.back();
    ++_tmp_color[3], _color.eb(_tmp_color);
    cerr << _color.back() << "[";
    for (bool _first = true; auto &_x : _t) {
        if (!_first) cerr << ", ";
        _print_err(_x), _first = false;
    }
    cerr << "]" << (_color.pb(), _color.back());
}

template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu) {
    string _tmp_color = _color.back();
    ++_tmp_color[3], _color.eb(_tmp_color);
    cerr << _color.back() << "(";
    _print_err(_tu.first), cerr << ", ", _print_err(_tu.second);
    cerr << ")" << (_color.pb(), _color.back());
    return os;
}

template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &) {
    cerr << ")" << (_color.pb(), _color.back());
}

template <size_t I = 0, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(const tuple<U...> &_t) {
    if (!I) {
        string _tmp_color = _color.back();
        ++_tmp_color[3], _color.eb(_tmp_color);
        cerr << _color.back();
    }
    cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}

template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &) {
    cerr << ")" << (_color.pb(), _color.back());
}

template <size_t I = 0, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(tuple<U...> &_t) {
    if (!I) {
        string _tmp_color = _color.back();
        ++_tmp_color[3], _color.eb(_tmp_color);
        cerr << _color.back();
    }
    cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}

#endif

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 324 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 328 KB Output is correct
27 Correct 1 ms 324 KB Output is correct
28 Correct 1 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 324 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 328 KB Output is correct
27 Correct 1 ms 324 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 2 ms 600 KB Output is correct
30 Correct 3 ms 724 KB Output is correct
31 Correct 4 ms 656 KB Output is correct
32 Correct 4 ms 596 KB Output is correct
33 Correct 4 ms 468 KB Output is correct
34 Correct 5 ms 596 KB Output is correct
35 Correct 3 ms 724 KB Output is correct
36 Correct 5 ms 592 KB Output is correct
37 Correct 3 ms 724 KB Output is correct
38 Correct 2 ms 980 KB Output is correct
39 Correct 3 ms 724 KB Output is correct
40 Correct 2 ms 596 KB Output is correct
41 Correct 3 ms 596 KB Output is correct
42 Correct 3 ms 596 KB Output is correct
43 Correct 3 ms 596 KB Output is correct
44 Correct 3 ms 596 KB Output is correct
45 Correct 3 ms 596 KB Output is correct
46 Correct 4 ms 724 KB Output is correct
47 Correct 3 ms 596 KB Output is correct
48 Correct 3 ms 600 KB Output is correct
49 Correct 4 ms 596 KB Output is correct
50 Correct 4 ms 724 KB Output is correct
51 Correct 3 ms 596 KB Output is correct
52 Correct 3 ms 560 KB Output is correct
53 Correct 3 ms 600 KB Output is correct
54 Correct 3 ms 724 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 778 ms 32764 KB Output is correct
4 Correct 125 ms 65772 KB Output is correct
5 Correct 372 ms 42952 KB Output is correct
6 Correct 288 ms 30228 KB Output is correct
7 Correct 273 ms 30288 KB Output is correct
8 Correct 269 ms 30600 KB Output is correct
9 Correct 370 ms 30776 KB Output is correct
10 Correct 609 ms 37280 KB Output is correct
11 Correct 407 ms 29628 KB Output is correct
12 Correct 484 ms 34868 KB Output is correct
13 Correct 256 ms 30720 KB Output is correct
14 Correct 264 ms 31000 KB Output is correct
15 Correct 458 ms 32208 KB Output is correct
16 Correct 630 ms 37672 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 324 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 328 KB Output is correct
27 Correct 1 ms 324 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 778 ms 32764 KB Output is correct
30 Correct 125 ms 65772 KB Output is correct
31 Correct 372 ms 42952 KB Output is correct
32 Correct 288 ms 30228 KB Output is correct
33 Correct 273 ms 30288 KB Output is correct
34 Correct 269 ms 30600 KB Output is correct
35 Correct 370 ms 30776 KB Output is correct
36 Correct 609 ms 37280 KB Output is correct
37 Correct 407 ms 29628 KB Output is correct
38 Correct 484 ms 34868 KB Output is correct
39 Correct 256 ms 30720 KB Output is correct
40 Correct 264 ms 31000 KB Output is correct
41 Correct 458 ms 32208 KB Output is correct
42 Correct 630 ms 37672 KB Output is correct
43 Correct 777 ms 34352 KB Output is correct
44 Correct 131 ms 66220 KB Output is correct
45 Correct 325 ms 47056 KB Output is correct
46 Correct 246 ms 31880 KB Output is correct
47 Correct 248 ms 30008 KB Output is correct
48 Correct 403 ms 31476 KB Output is correct
49 Correct 637 ms 37840 KB Output is correct
50 Correct 382 ms 30684 KB Output is correct
51 Correct 520 ms 32688 KB Output is correct
52 Correct 627 ms 40260 KB Output is correct
53 Correct 246 ms 30516 KB Output is correct
54 Correct 293 ms 31092 KB Output is correct
55 Correct 479 ms 32352 KB Output is correct
56 Correct 599 ms 38044 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 324 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 328 KB Output is correct
27 Correct 1 ms 324 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 2 ms 600 KB Output is correct
30 Correct 3 ms 724 KB Output is correct
31 Correct 4 ms 656 KB Output is correct
32 Correct 4 ms 596 KB Output is correct
33 Correct 4 ms 468 KB Output is correct
34 Correct 5 ms 596 KB Output is correct
35 Correct 3 ms 724 KB Output is correct
36 Correct 5 ms 592 KB Output is correct
37 Correct 3 ms 724 KB Output is correct
38 Correct 2 ms 980 KB Output is correct
39 Correct 3 ms 724 KB Output is correct
40 Correct 2 ms 596 KB Output is correct
41 Correct 3 ms 596 KB Output is correct
42 Correct 3 ms 596 KB Output is correct
43 Correct 3 ms 596 KB Output is correct
44 Correct 3 ms 596 KB Output is correct
45 Correct 3 ms 596 KB Output is correct
46 Correct 4 ms 724 KB Output is correct
47 Correct 3 ms 596 KB Output is correct
48 Correct 3 ms 600 KB Output is correct
49 Correct 4 ms 596 KB Output is correct
50 Correct 4 ms 724 KB Output is correct
51 Correct 3 ms 596 KB Output is correct
52 Correct 3 ms 560 KB Output is correct
53 Correct 3 ms 600 KB Output is correct
54 Correct 3 ms 724 KB Output is correct
55 Correct 737 ms 31752 KB Output is correct
56 Correct 107 ms 64052 KB Output is correct
57 Correct 317 ms 43856 KB Output is correct
58 Correct 239 ms 29204 KB Output is correct
59 Correct 289 ms 28148 KB Output is correct
60 Correct 531 ms 30948 KB Output is correct
61 Correct 364 ms 27864 KB Output is correct
62 Correct 509 ms 34816 KB Output is correct
63 Correct 231 ms 28700 KB Output is correct
64 Correct 426 ms 29264 KB Output is correct
65 Correct 467 ms 32976 KB Output is correct

Subtask #6
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 324 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 328 KB Output is correct
27 Correct 1 ms 324 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 2 ms 600 KB Output is correct
30 Correct 3 ms 724 KB Output is correct
31 Correct 4 ms 656 KB Output is correct
32 Correct 4 ms 596 KB Output is correct
33 Correct 4 ms 468 KB Output is correct
34 Correct 5 ms 596 KB Output is correct
35 Correct 3 ms 724 KB Output is correct
36 Correct 5 ms 592 KB Output is correct
37 Correct 3 ms 724 KB Output is correct
38 Correct 2 ms 980 KB Output is correct
39 Correct 3 ms 724 KB Output is correct
40 Correct 2 ms 596 KB Output is correct
41 Correct 3 ms 596 KB Output is correct
42 Correct 3 ms 596 KB Output is correct
43 Correct 3 ms 596 KB Output is correct
44 Correct 3 ms 596 KB Output is correct
45 Correct 3 ms 596 KB Output is correct
46 Correct 4 ms 724 KB Output is correct
47 Correct 3 ms 596 KB Output is correct
48 Correct 3 ms 600 KB Output is correct
49 Correct 4 ms 596 KB Output is correct
50 Correct 4 ms 724 KB Output is correct
51 Correct 3 ms 596 KB Output is correct
52 Correct 3 ms 560 KB Output is correct
53 Correct 3 ms 600 KB Output is correct
54 Correct 3 ms 724 KB Output is correct
55 Correct 778 ms 32764 KB Output is correct
56 Correct 125 ms 65772 KB Output is correct
57 Correct 372 ms 42952 KB Output is correct
58 Correct 288 ms 30228 KB Output is correct
59 Correct 273 ms 30288 KB Output is correct
60 Correct 269 ms 30600 KB Output is correct
61 Correct 370 ms 30776 KB Output is correct
62 Correct 609 ms 37280 KB Output is correct
63 Correct 407 ms 29628 KB Output is correct
64 Correct 484 ms 34868 KB Output is correct
65 Correct 256 ms 30720 KB Output is correct
66 Correct 264 ms 31000 KB Output is correct
67 Correct 458 ms 32208 KB Output is correct
68 Correct 630 ms 37672 KB Output is correct
69 Correct 777 ms 34352 KB Output is correct
70 Correct 131 ms 66220 KB Output is correct
71 Correct 325 ms 47056 KB Output is correct
72 Correct 246 ms 31880 KB Output is correct
73 Correct 248 ms 30008 KB Output is correct
74 Correct 403 ms 31476 KB Output is correct
75 Correct 637 ms 37840 KB Output is correct
76 Correct 382 ms 30684 KB Output is correct
77 Correct 520 ms 32688 KB Output is correct
78 Correct 627 ms 40260 KB Output is correct
79 Correct 246 ms 30516 KB Output is correct
80 Correct 293 ms 31092 KB Output is correct
81 Correct 479 ms 32352 KB Output is correct
82 Correct 599 ms 38044 KB Output is correct
83 Correct 737 ms 31752 KB Output is correct
84 Correct 107 ms 64052 KB Output is correct
85 Correct 317 ms 43856 KB Output is correct
86 Correct 239 ms 29204 KB Output is correct
87 Correct 289 ms 28148 KB Output is correct
88 Correct 531 ms 30948 KB Output is correct
89 Correct 364 ms 27864 KB Output is correct
90 Correct 509 ms 34816 KB Output is correct
91 Correct 231 ms 28700 KB Output is correct
92 Correct 426 ms 29264 KB Output is correct
93 Correct 467 ms 32976 KB Output is correct
94 Correct 769 ms 34988 KB Output is correct
95 Correct 499 ms 54668 KB Output is correct
96 Correct 324 ms 46352 KB Output is correct
97 Correct 261 ms 33328 KB Output is correct
98 Correct 233 ms 30992 KB Output is correct
99 Correct 298 ms 31724 KB Output is correct
100 Correct 532 ms 38704 KB Output is correct
101 Correct 389 ms 30256 KB Output is correct
102 Correct 475 ms 33812 KB Output is correct
103 Correct 544 ms 38960 KB Output is correct
104 Correct 269 ms 31864 KB Output is correct
105 Correct 438 ms 32336 KB Output is correct
106 Correct 650 ms 36152 KB Output is correct
107 Correct 199 ms 45108 KB Output is correct
108 Correct 756 ms 34924 KB Output is correct
109 Correct 787 ms 34804 KB Output is correct
110 Correct 745 ms 34832 KB Output is correct
111 Correct 742 ms 34832 KB Output is correct
112 Correct 753 ms 34860 KB Output is correct
113 Correct 747 ms 34820 KB Output is correct
114 Correct 761 ms 34732 KB Output is correct
115 Correct 750 ms 34732 KB Output is correct
116 Correct 792 ms 34916 KB Output is correct