oj.uz

Submission #201225

# Submission time Handle Problem Language Result Execution time Memory
201225 2020-02-09T21:07:54 Z darkkcyan Segments (IZhO18_segments) C++17
100 / 100
 4644 ms 29348 KB 
// vim: foldmethod=marker
// Sun Feb  9 11:53:54 MSK 2020: START coding
// Sun Feb  9 12:04:53 MSK 2020: PAUSE
// Sun Feb  9 12:10:50 MSK 2020: CONTINUE
// Sun Feb  9 13:05:32 MSK 2020
#include <bits/stdc++.h>
using namespace std;

#define llong long long 
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define rand __rand
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
template<class T = int> T rand(T range = numeric_limits<T>::max()) { return (T)(rng() % range); }

/*{{{*/
#define CONCAT_(x, y) x##y
#define CONCAT(x, y) CONCAT_(x, y)
#ifdef LOCAL_DEBUG   
int debug = 1;
#define DB(...) stringstream CONCAT(ss, __LINE__); CONCAT(ss, __LINE__) << __VA_ARGS__; debug_block CONCAT(dbbl, __LINE__)(CONCAT(ss, __LINE__).str())
#else
int debug = 0;
#define DB(...)
#endif
int __db_level = 0;
#define clog if (debug) cerr << string(__db_level * 2, ' ')
struct debug_block {
    string name;
    debug_block(const string& name_): name(name_) { clog << "{ " << name << endl; ++__db_level; }
    ~debug_block() { --__db_level; clog << "} " << name << endl; }
};
#define deb(...) "[" << #__VA_ARGS__ << "] = [" << __VA_ARGS__ << "]"
#define debln(...)  clog << "[" << #__VA_ARGS__ << "] = [" << __VA_ARGS__ << "]" << endl
#define _ << ", " <<
template<class U, class V>
ostream& operator<<(ostream& out, const pair<U, V>& p) { return out << "(" << p.first _ p.second << ")"; }
template<class A, class B>
ostream& operator<<(ostream& out, const tuple<A, B>& t) { return out << "(" << get<0>(t) _ get<1>(t) << ")"; }
template<class A, class B, class C>
ostream& operator<<(ostream& out, const tuple<A, B, C>& t) { return out << "(" << get<0>(t) _ get<1>(t) _ get<2>(t) << ")"; }
template<class T> ostream& operator<<(ostream& out, const vector<T>& container) { 
    out << "{";
    if (len(container)) out << container[0];
    rep1(i, len(container) - 1) out _ container[i];
    return out << "}";
}
template<class x> vector<typename x::value_type> $v(const x& a) { return vector<typename x::value_type>(a.begin(), a.end()); }
#define ptrtype(x) typename iterator_traits<x>::value_type
template<class u> vector<ptrtype(u)> $v(u a, u b) { return vector<ptrtype(u)>(a, b); }
/*}}}*/
// ACTUAL SOLUTION BELOW ////////////////////////////////////////////////////////////

#ifdef LOCAL
const int bucket_size = 3;  // for testing
#else
const int bucket_size = 447;
#endif
const int maxn = 200'100;
struct segment {
    llong l, r;

    segment() = default;
    segment(llong l_, llong r_) : l(l_), r(r_) {}
    inline llong length() const { return r - l + 1; }

    friend llong cnt_intersect(const segment& lhs, const segment& rhs) {
        if (lhs.l > rhs.r or rhs.l > lhs.r) return 0;
        return min(lhs.r, rhs.r) - max(lhs.l, rhs.l) + 1;
    }

    bool is_removed() { return l > r; }

    static bool cmp_by_length(const segment& u, const segment& v) { return u.length() < v.length(); }
    static bool cmp_by_left(const segment& u, const segment& v) { return u.l < v.l; }
    static bool cmp_by_right(const segment& u, const segment& v) { return u.r < v.r; }
};

ostream& operator<<(ostream& out, const segment& seg) {
    return out << "segment(" <<
        "l = " << seg.l _
        "r = " << seg.r << 
        ")";
}

template<class T>
function<bool(T*, T*)> cmp_ptr(const function<bool(const T& u, const T& v)>& cmp_ref) {
    return [&](T* u, T* v) -> bool { return cmp_ref(*u, *v); };
}


struct bucket {
    llong min_length, max_length;
    vector<segment> left, right;
    bucket() {}

    template<class iter>
    void assign(iter beg, iter end) {
        left.clear();
        right.clear();
        int dst = (int)distance(beg, end);
        left.reserve(dst);
        right.reserve(dst);
        min_length = min_element(beg, end, segment::cmp_by_length)->length();
        max_length = max_element(beg, end, segment::cmp_by_length)->length();
        for (; beg < end; ++beg) {
            left.push_back(*beg);
            right.push_back(*beg);
        }
    
        sort(left.begin(), left.end(), segment::cmp_by_left);
        sort(right.begin(), right.end(), segment::cmp_by_right);
    }

    int query(segment const& qr, llong k) {
        if (k == 0) return len(left);
        if (max_length < k) return 0;
        if (min_length <= k and k <= max_length and max_length != min_length) {
            int ans = len(left);
            for (auto& seg: left) {
                if (cnt_intersect(seg, qr) < k) -- ans;
            }
            return ans;
        }

        segment upper_left(qr.r - k + 1, qr.r), lower_right(qr.l, qr.l + k - 1);

        return len(left) - (int)(
            (left.end() -  upper_bound(left.begin(), left.end(), upper_left, segment::cmp_by_left)) + 
            (lower_bound(right.begin(), right.end(), lower_right, segment::cmp_by_right) - right.begin())
        );
    }
};

int max_unassigned = 1;
list<segment> all_segments;
list<segment>::iterator seg_id[maxn];

int n_bucket = 0;
bucket buckets[maxn / bucket_size + 10];

vector<segment> current_removed, current_added;

void rebuild() {
    current_removed.clear();
    current_added.clear();

    vector<segment> avaliable_seg(all_segments.begin(), all_segments.end());
    sort(avaliable_seg.begin(), avaliable_seg.end(), segment::cmp_by_length);

    n_bucket = 0;
    for (int i = 0; i < len(avaliable_seg); i += bucket_size)
        buckets[n_bucket++].assign(avaliable_seg.begin() + i, avaliable_seg.begin() + min(i + bucket_size, len(avaliable_seg)));
}

void do_add(const segment& new_seg) { 
    all_segments.push_back(new_seg);
    seg_id[max_unassigned++] = --all_segments.end();
    current_added.push_back(new_seg);
}

void do_remove(int id) {
    current_removed.push_back(*seg_id[id]);
    all_segments.erase(seg_id[id]);
}

int do_query(segment querying_seg, llong k) {
    if (querying_seg.length() < k) return 0;
    int ans = 0;
    rep(i, n_bucket) ans += buckets[i].query(querying_seg, k);

    for (auto& seg: current_added) 
        if (cnt_intersect(seg, querying_seg) >= k) ++ans;
    for (auto& seg: current_removed) 
        if (cnt_intersect(seg, querying_seg) >= k) --ans;
    return ans;
}

struct stdio_interactor {
    int n, t;
    int last_ans = 0;
    stdio_interactor() { scanf("%d %d", &n, &t); }

    inline tuple<int, segment, llong> get_query() {
        int qr_type;
        segment new_seg; 
        llong num;
        scanf("%d", &qr_type);
        if (qr_type == 1 or qr_type == 3) {
            llong l, r; scanf("%lld %lld", &l, &r);
            l ^= t * last_ans;
            r ^= t * last_ans;
            if (l > r) swap(l, r);
            new_seg = segment(l, r);
        }
        if (qr_type == 2 or qr_type == 3) scanf("%lld", &num);
        return {qr_type, new_seg, num};
    }

    inline void answer(int cur_ans) {
        printf("%d\n", cur_ans);
        last_ans = cur_ans;
    }
};

struct test_interactor {
    int n = 3;
    ofstream inp;
    map<int, segment> having_segments;
    set<int> removed;
    int current_ans = -1;

    test_interactor(): inp("test.inp") {
        inp << n << ' ' << 0 << endl;
    }

    ~test_interactor() {
        if (current_ans != -1) {
            clog << "not answering the last query" << endl;
        }
    }

    segment rand_seg() {
        auto l = rand(2'000'000'000L), r = rand(2'000'000'000L);
        if (l > r) swap(l, r);
        return segment(l, r);
    }

    tuple<int, segment, llong> get_query() {
        if (current_ans != -1) {
            clog << "Not answering the previous query" << endl;
            exit(0);
        }

        int qr_type;
        do {
            qr_type = rand(3) + 1;
        } while (qr_type == 2 and !having_segments.size());

        inp << qr_type << ' ';
        segment seg; llong num;
        if (qr_type == 1) {
            seg = rand_seg();
            having_segments[len(having_segments) + 1] = seg;
            inp << seg.l << ' ' << seg.r << endl;
        } else if (qr_type == 2) {
            do {
                num = rand(having_segments.size()) + 2;
            } while (removed.count((int)num));
            removed.insert((int)num);
            inp << num << endl;
        } else {
            seg = rand_seg();
            num = rand(2'000'000'000L);
            current_ans = 0;
            for (auto [id, hseg]: having_segments) {
                if (removed.count(id)) continue;
                current_ans += cnt_intersect(hseg, seg) >= num;
            }
            inp << seg.l << ' ' << seg.r << ' ' << num << endl;
        }
        return {qr_type, seg, num};
    }

    inline void answer(int ans) {
        if (current_ans == -1) {
            clog << "The query does not need to be asnwer" << endl;
            exit(0);
        }
        if (current_ans != ans) {
            clog << "Different answer: " << endl;
            debln(current_ans);
            debln(ans);
            exit(0);
        }
        current_ans = -1;
    }
};

int main(void) {
    // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    stdio_interactor interactor;          
    // test_interactor interactor;          

    rep1(nquery, interactor.n) {
        auto [qr_type, new_seg, num] = interactor.get_query();
        if (qr_type == 1) do_add(new_seg);
        else if (qr_type == 2) do_remove((int)num);
        else if (qr_type == 3) {
            if (len(current_added) + len(current_removed) >= bucket_size)
                rebuild();
            interactor.answer(do_query(new_seg, num));
        }
        else assert(false);

    }

    return 0;
}

Compilation message

segments.cpp: In constructor 'stdio_interactor::stdio_interactor()':
segments.cpp:183:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     stdio_interactor() { scanf("%d %d", &n, &t); }
                          ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp: In member function 'std::tuple<int, segment, long long int> stdio_interactor::get_query()':
segments.cpp:189:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &qr_type);
         ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:191:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             llong l, r; scanf("%lld %lld", &l, &r);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~
segments.cpp:197:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         if (qr_type == 2 or qr_type == 3) scanf("%lld", &num);
                                           ~~~~~^~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1912 KB Output is correct
2 Correct 6 ms 1912 KB Output is correct
3 Correct 10 ms 1912 KB Output is correct
4 Correct 10 ms 2040 KB Output is correct
5 Correct 11 ms 2424 KB Output is correct
6 Correct 12 ms 2424 KB Output is correct
7 Correct 12 ms 2040 KB Output is correct
8 Correct 13 ms 2388 KB Output is correct
9 Correct 13 ms 2300 KB Output is correct
10 Correct 10 ms 2424 KB Output is correct
11 Correct 13 ms 2296 KB Output is correct
12 Correct 12 ms 2296 KB Output is correct
13 Correct 10 ms 2428 KB Output is correct
14 Correct 13 ms 2296 KB Output is correct
15 Correct 10 ms 1912 KB Output is correct
16 Correct 11 ms 2040 KB Output is correct
17 Correct 14 ms 2168 KB Output is correct
18 Correct 11 ms 2424 KB Output is correct
19 Correct 14 ms 2168 KB Output is correct
20 Correct 12 ms 2168 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 7404 KB Output is correct
2 Correct 533 ms 7784 KB Output is correct
3 Correct 542 ms 7784 KB Output is correct
4 Correct 525 ms 8300 KB Output is correct
5 Correct 187 ms 12644 KB Output is correct
6 Correct 139 ms 12900 KB Output is correct
7 Correct 539 ms 7788 KB Output is correct
8 Correct 549 ms 7784 KB Output is correct
9 Correct 552 ms 7784 KB Output is correct
10 Correct 401 ms 4544 KB Output is correct
11 Correct 474 ms 5448 KB Output is correct
12 Correct 450 ms 9960 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 2040 KB Output is correct
2 Correct 101 ms 2168 KB Output is correct
3 Correct 118 ms 2296 KB Output is correct
4 Correct 103 ms 2296 KB Output is correct
5 Correct 551 ms 9956 KB Output is correct
6 Correct 627 ms 8812 KB Output is correct
7 Correct 594 ms 9700 KB Output is correct
8 Correct 207 ms 12516 KB Output is correct
9 Correct 481 ms 12004 KB Output is correct
10 Correct 1119 ms 10352 KB Output is correct
11 Correct 256 ms 2828 KB Output is correct
12 Correct 1090 ms 9932 KB Output is correct
13 Correct 1135 ms 9440 KB Output is correct
14 Correct 929 ms 6096 KB Output is correct
15 Correct 854 ms 5148 KB Output is correct
16 Correct 642 ms 4440 KB Output is correct
17 Correct 655 ms 7660 KB Output is correct
18 Correct 654 ms 7656 KB Output is correct
19 Correct 696 ms 7788 KB Output is correct
20 Correct 663 ms 7788 KB Output is correct
21 Correct 308 ms 3064 KB Output is correct
22 Correct 1128 ms 7176 KB Output is correct
23 Correct 1211 ms 8440 KB Output is correct
24 Correct 1148 ms 7588 KB Output is correct
25 Correct 107 ms 2424 KB Output is correct
26 Correct 100 ms 2424 KB Output is correct
27 Correct 107 ms 2428 KB Output is correct
28 Correct 100 ms 2424 KB Output is correct
29 Correct 1218 ms 9384 KB Output is correct
30 Correct 1220 ms 9236 KB Output is correct
31 Correct 465 ms 13864 KB Output is correct
32 Correct 1112 ms 10472 KB Output is correct
33 Correct 1126 ms 9980 KB Output is correct
34 Correct 828 ms 5544 KB Output is correct
35 Correct 1166 ms 8632 KB Output is correct
36 Correct 1101 ms 9504 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 2040 KB Output is correct
2 Correct 108 ms 2168 KB Output is correct
3 Correct 102 ms 2296 KB Output is correct
4 Correct 111 ms 2296 KB Output is correct
5 Correct 407 ms 10608 KB Output is correct
6 Correct 347 ms 3996 KB Output is correct
7 Correct 343 ms 11236 KB Output is correct
8 Correct 415 ms 4536 KB Output is correct
9 Correct 1077 ms 6772 KB Output is correct
10 Correct 997 ms 11288 KB Output is correct
11 Correct 574 ms 4208 KB Output is correct
12 Correct 291 ms 12560 KB Output is correct
13 Correct 1151 ms 9572 KB Output is correct
14 Correct 993 ms 6336 KB Output is correct
15 Correct 517 ms 13544 KB Output is correct
16 Correct 1113 ms 10048 KB Output is correct
17 Correct 530 ms 7656 KB Output is correct
18 Correct 534 ms 7660 KB Output is correct
19 Correct 535 ms 7532 KB Output is correct
20 Correct 538 ms 7660 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1912 KB Output is correct
2 Correct 6 ms 1912 KB Output is correct
3 Correct 10 ms 1912 KB Output is correct
4 Correct 10 ms 2040 KB Output is correct
5 Correct 11 ms 2424 KB Output is correct
6 Correct 12 ms 2424 KB Output is correct
7 Correct 12 ms 2040 KB Output is correct
8 Correct 13 ms 2388 KB Output is correct
9 Correct 13 ms 2300 KB Output is correct
10 Correct 10 ms 2424 KB Output is correct
11 Correct 13 ms 2296 KB Output is correct
12 Correct 12 ms 2296 KB Output is correct
13 Correct 10 ms 2428 KB Output is correct
14 Correct 13 ms 2296 KB Output is correct
15 Correct 10 ms 1912 KB Output is correct
16 Correct 11 ms 2040 KB Output is correct
17 Correct 14 ms 2168 KB Output is correct
18 Correct 11 ms 2424 KB Output is correct
19 Correct 14 ms 2168 KB Output is correct
20 Correct 12 ms 2168 KB Output is correct
21 Correct 537 ms 7404 KB Output is correct
22 Correct 533 ms 7784 KB Output is correct
23 Correct 542 ms 7784 KB Output is correct
24 Correct 525 ms 8300 KB Output is correct
25 Correct 187 ms 12644 KB Output is correct
26 Correct 139 ms 12900 KB Output is correct
27 Correct 539 ms 7788 KB Output is correct
28 Correct 549 ms 7784 KB Output is correct
29 Correct 552 ms 7784 KB Output is correct
30 Correct 401 ms 4544 KB Output is correct
31 Correct 474 ms 5448 KB Output is correct
32 Correct 450 ms 9960 KB Output is correct
33 Correct 101 ms 2040 KB Output is correct
34 Correct 108 ms 2168 KB Output is correct
35 Correct 102 ms 2296 KB Output is correct
36 Correct 111 ms 2296 KB Output is correct
37 Correct 407 ms 10608 KB Output is correct
38 Correct 347 ms 3996 KB Output is correct
39 Correct 343 ms 11236 KB Output is correct
40 Correct 415 ms 4536 KB Output is correct
41 Correct 1077 ms 6772 KB Output is correct
42 Correct 997 ms 11288 KB Output is correct
43 Correct 574 ms 4208 KB Output is correct
44 Correct 291 ms 12560 KB Output is correct
45 Correct 1151 ms 9572 KB Output is correct
46 Correct 993 ms 6336 KB Output is correct
47 Correct 517 ms 13544 KB Output is correct
48 Correct 1113 ms 10048 KB Output is correct
49 Correct 530 ms 7656 KB Output is correct
50 Correct 534 ms 7660 KB Output is correct
51 Correct 535 ms 7532 KB Output is correct
52 Correct 538 ms 7660 KB Output is correct
53 Correct 111 ms 2424 KB Output is correct
54 Correct 113 ms 2424 KB Output is correct
55 Correct 110 ms 2424 KB Output is correct
56 Correct 105 ms 2424 KB Output is correct
57 Correct 498 ms 5740 KB Output is correct
58 Correct 284 ms 3812 KB Output is correct
59 Correct 499 ms 9068 KB Output is correct
60 Correct 259 ms 3576 KB Output is correct
61 Correct 1164 ms 9848 KB Output is correct
62 Correct 613 ms 13212 KB Output is correct
63 Correct 373 ms 12472 KB Output is correct
64 Correct 588 ms 13424 KB Output is correct
65 Correct 733 ms 4876 KB Output is correct
66 Correct 604 ms 4432 KB Output is correct
67 Correct 1098 ms 9368 KB Output is correct
68 Correct 1153 ms 8676 KB Output is correct
69 Correct 542 ms 7784 KB Output is correct
70 Correct 531 ms 7916 KB Output is correct
71 Correct 533 ms 7788 KB Output is correct
72 Correct 531 ms 7784 KB Output is correct
73 Correct 843 ms 5384 KB Output is correct
74 Correct 1152 ms 8528 KB Output is correct
75 Correct 182 ms 13028 KB Output is correct
76 Correct 350 ms 13996 KB Output is correct
77 Correct 106 ms 2424 KB Output is correct
78 Correct 103 ms 2424 KB Output is correct
79 Correct 109 ms 2424 KB Output is correct
80 Correct 109 ms 2428 KB Output is correct
81 Correct 1165 ms 8004 KB Output is correct
82 Correct 849 ms 5392 KB Output is correct
83 Correct 549 ms 3964 KB Output is correct
84 Correct 1163 ms 8360 KB Output is correct
85 Correct 1093 ms 10252 KB Output is correct
86 Correct 1073 ms 10732 KB Output is correct
87 Correct 1059 ms 6460 KB Output is correct
88 Correct 551 ms 4012 KB Output is correct

Subtask #6
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1912 KB Output is correct
2 Correct 6 ms 1912 KB Output is correct
3 Correct 10 ms 1912 KB Output is correct
4 Correct 10 ms 2040 KB Output is correct
5 Correct 11 ms 2424 KB Output is correct
6 Correct 12 ms 2424 KB Output is correct
7 Correct 12 ms 2040 KB Output is correct
8 Correct 13 ms 2388 KB Output is correct
9 Correct 13 ms 2300 KB Output is correct
10 Correct 10 ms 2424 KB Output is correct
11 Correct 13 ms 2296 KB Output is correct
12 Correct 12 ms 2296 KB Output is correct
13 Correct 10 ms 2428 KB Output is correct
14 Correct 13 ms 2296 KB Output is correct
15 Correct 10 ms 1912 KB Output is correct
16 Correct 11 ms 2040 KB Output is correct
17 Correct 14 ms 2168 KB Output is correct
18 Correct 11 ms 2424 KB Output is correct
19 Correct 14 ms 2168 KB Output is correct
20 Correct 12 ms 2168 KB Output is correct
21 Correct 537 ms 7404 KB Output is correct
22 Correct 533 ms 7784 KB Output is correct
23 Correct 542 ms 7784 KB Output is correct
24 Correct 525 ms 8300 KB Output is correct
25 Correct 187 ms 12644 KB Output is correct
26 Correct 139 ms 12900 KB Output is correct
27 Correct 539 ms 7788 KB Output is correct
28 Correct 549 ms 7784 KB Output is correct
29 Correct 552 ms 7784 KB Output is correct
30 Correct 401 ms 4544 KB Output is correct
31 Correct 474 ms 5448 KB Output is correct
32 Correct 450 ms 9960 KB Output is correct
33 Correct 101 ms 2040 KB Output is correct
34 Correct 101 ms 2168 KB Output is correct
35 Correct 118 ms 2296 KB Output is correct
36 Correct 103 ms 2296 KB Output is correct
37 Correct 551 ms 9956 KB Output is correct
38 Correct 627 ms 8812 KB Output is correct
39 Correct 594 ms 9700 KB Output is correct
40 Correct 207 ms 12516 KB Output is correct
41 Correct 481 ms 12004 KB Output is correct
42 Correct 1119 ms 10352 KB Output is correct
43 Correct 256 ms 2828 KB Output is correct
44 Correct 1090 ms 9932 KB Output is correct
45 Correct 1135 ms 9440 KB Output is correct
46 Correct 929 ms 6096 KB Output is correct
47 Correct 854 ms 5148 KB Output is correct
48 Correct 642 ms 4440 KB Output is correct
49 Correct 655 ms 7660 KB Output is correct
50 Correct 654 ms 7656 KB Output is correct
51 Correct 696 ms 7788 KB Output is correct
52 Correct 663 ms 7788 KB Output is correct
53 Correct 308 ms 3064 KB Output is correct
54 Correct 1128 ms 7176 KB Output is correct
55 Correct 1211 ms 8440 KB Output is correct
56 Correct 1148 ms 7588 KB Output is correct
57 Correct 107 ms 2424 KB Output is correct
58 Correct 100 ms 2424 KB Output is correct
59 Correct 107 ms 2428 KB Output is correct
60 Correct 100 ms 2424 KB Output is correct
61 Correct 1218 ms 9384 KB Output is correct
62 Correct 1220 ms 9236 KB Output is correct
63 Correct 465 ms 13864 KB Output is correct
64 Correct 1112 ms 10472 KB Output is correct
65 Correct 1126 ms 9980 KB Output is correct
66 Correct 828 ms 5544 KB Output is correct
67 Correct 1166 ms 8632 KB Output is correct
68 Correct 1101 ms 9504 KB Output is correct
69 Correct 101 ms 2040 KB Output is correct
70 Correct 108 ms 2168 KB Output is correct
71 Correct 102 ms 2296 KB Output is correct
72 Correct 111 ms 2296 KB Output is correct
73 Correct 407 ms 10608 KB Output is correct
74 Correct 347 ms 3996 KB Output is correct
75 Correct 343 ms 11236 KB Output is correct
76 Correct 415 ms 4536 KB Output is correct
77 Correct 1077 ms 6772 KB Output is correct
78 Correct 997 ms 11288 KB Output is correct
79 Correct 574 ms 4208 KB Output is correct
80 Correct 291 ms 12560 KB Output is correct
81 Correct 1151 ms 9572 KB Output is correct
82 Correct 993 ms 6336 KB Output is correct
83 Correct 517 ms 13544 KB Output is correct
84 Correct 1113 ms 10048 KB Output is correct
85 Correct 530 ms 7656 KB Output is correct
86 Correct 534 ms 7660 KB Output is correct
87 Correct 535 ms 7532 KB Output is correct
88 Correct 538 ms 7660 KB Output is correct
89 Correct 111 ms 2424 KB Output is correct
90 Correct 113 ms 2424 KB Output is correct
91 Correct 110 ms 2424 KB Output is correct
92 Correct 105 ms 2424 KB Output is correct
93 Correct 498 ms 5740 KB Output is correct
94 Correct 284 ms 3812 KB Output is correct
95 Correct 499 ms 9068 KB Output is correct
96 Correct 259 ms 3576 KB Output is correct
97 Correct 1164 ms 9848 KB Output is correct
98 Correct 613 ms 13212 KB Output is correct
99 Correct 373 ms 12472 KB Output is correct
100 Correct 588 ms 13424 KB Output is correct
101 Correct 733 ms 4876 KB Output is correct
102 Correct 604 ms 4432 KB Output is correct
103 Correct 1098 ms 9368 KB Output is correct
104 Correct 1153 ms 8676 KB Output is correct
105 Correct 542 ms 7784 KB Output is correct
106 Correct 531 ms 7916 KB Output is correct
107 Correct 533 ms 7788 KB Output is correct
108 Correct 531 ms 7784 KB Output is correct
109 Correct 843 ms 5384 KB Output is correct
110 Correct 1152 ms 8528 KB Output is correct
111 Correct 182 ms 13028 KB Output is correct
112 Correct 350 ms 13996 KB Output is correct
113 Correct 106 ms 2424 KB Output is correct
114 Correct 103 ms 2424 KB Output is correct
115 Correct 109 ms 2424 KB Output is correct
116 Correct 109 ms 2428 KB Output is correct
117 Correct 1165 ms 8004 KB Output is correct
118 Correct 849 ms 5392 KB Output is correct
119 Correct 549 ms 3964 KB Output is correct
120 Correct 1163 ms 8360 KB Output is correct
121 Correct 1093 ms 10252 KB Output is correct
122 Correct 1073 ms 10732 KB Output is correct
123 Correct 1059 ms 6460 KB Output is correct
124 Correct 551 ms 4012 KB Output is correct
125 Correct 217 ms 2552 KB Output is correct
126 Correct 229 ms 2528 KB Output is correct
127 Correct 256 ms 2552 KB Output is correct
128 Correct 226 ms 2564 KB Output is correct
129 Correct 209 ms 2552 KB Output is correct
130 Correct 232 ms 2552 KB Output is correct
131 Correct 884 ms 5048 KB Output is correct
132 Correct 1848 ms 12016 KB Output is correct
133 Correct 1723 ms 16604 KB Output is correct
134 Correct 1215 ms 12140 KB Output is correct
135 Correct 1579 ms 20572 KB Output is correct
136 Correct 423 ms 9592 KB Output is correct
137 Correct 2075 ms 28576 KB Output is correct
138 Correct 4619 ms 20076 KB Output is correct
139 Correct 3888 ms 24036 KB Output is correct
140 Correct 2757 ms 27512 KB Output is correct
141 Correct 4442 ms 22420 KB Output is correct
142 Correct 1069 ms 8164 KB Output is correct
143 Correct 2749 ms 10668 KB Output is correct
144 Correct 641 ms 7288 KB Output is correct
145 Correct 2792 ms 26572 KB Output is correct
146 Correct 4073 ms 15296 KB Output is correct
147 Correct 2902 ms 11624 KB Output is correct
148 Correct 2631 ms 11072 KB Output is correct
149 Correct 1904 ms 17488 KB Output is correct
150 Correct 1884 ms 17480 KB Output is correct
151 Correct 1868 ms 17604 KB Output is correct
152 Correct 1912 ms 17724 KB Output is correct
153 Correct 1901 ms 17732 KB Output is correct
154 Correct 1937 ms 17348 KB Output is correct
155 Correct 1817 ms 8804 KB Output is correct
156 Correct 3099 ms 11984 KB Output is correct
157 Correct 2639 ms 27428 KB Output is correct
158 Correct 2245 ms 28148 KB Output is correct
159 Correct 4619 ms 20508 KB Output is correct
160 Correct 4242 ms 14776 KB Output is correct
161 Correct 245 ms 6392 KB Output is correct
162 Correct 237 ms 6392 KB Output is correct
163 Correct 237 ms 6392 KB Output is correct
164 Correct 297 ms 6648 KB Output is correct
165 Correct 245 ms 6392 KB Output is correct
166 Correct 234 ms 6396 KB Output is correct
167 Correct 1568 ms 27196 KB Output is correct
168 Correct 1565 ms 29348 KB Output is correct
169 Correct 2784 ms 27324 KB Output is correct
170 Correct 3281 ms 23808 KB Output is correct
171 Correct 4427 ms 22176 KB Output is correct
172 Correct 3811 ms 14192 KB Output is correct
173 Correct 2538 ms 27708 KB Output is correct
174 Correct 4006 ms 14640 KB Output is correct
175 Correct 4204 ms 23136 KB Output is correct
176 Correct 2608 ms 10912 KB Output is correct
177 Correct 4635 ms 20228 KB Output is correct
178 Correct 4644 ms 19484 KB Output is correct