답안 #914860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
914860	2024-01-22T19:00:10 Z	vjudge1	송신탑 (IOI22_towers)	C++17	100 / 100	895 ms	56272 KB

towers

#include "towers.h"

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
using pl = pair<ll, ll>;
using vl = vector<ll>;
#define F(i, l, r) for (ll i = ll(l); i < ll(r); ++i)
#define FD(i, l, r) for (ll i = ll(l); i > ll(r); --i)
#define A(a) (a).begin(), (a).end()
#define K first
#define V second

template<typename T> struct SparseTable {
    int n,log2=0;
    function<T(T, T)> merge;
    T id ;
    vector<vector<T>> a = {{}};
    SparseTable(const vector<T>& v, function<T(T, T)> _merge, T _id): merge(_merge), id(_id) {
        n = v.size();
        while((1<<log2) <= n) {
            ++log2;
        }
        a.resize(log2);
        a[0] = v;
        for(int i=1,len=1;i<log2;++i,len*=2) {
            a[i].resize(n + 1 - (1<<i));
            for(size_t j=0;j<a[i].size();++j) {
                a[i][j] = merge(a[i-1][j], a[i-1][j + len]);
            }
        }
    }
    SparseTable(){}
    T query(int l, int r) { // [l,r)
        if (r <= l) return id;
        int len = __lg(r-l);
        return merge(a[len][l], a[len][r- (1<<len)]);
    }   
};

SparseTable<ll> spmin;
 

const int MAXN = 100010, INF = 1000000010;

namespace seg {
    pl merge(pl a, pl b) {
        return pair(min(a.K, b.K), max(a.V, b.V));
    }

    struct node{    
        vector<pl> vec;
        vector<pl> indices; // {mn, mx}
        node(){};
        node(int value, int pos){
            vec.emplace_back(value, pos);
            indices.emplace_back(pos, pos);
        }
        node(node& a, node& b){
            vec.resize(a.vec.size() + b.vec.size());
            indices.resize(vec.size());
            merge(a.vec.begin(), a.vec.end(), b.vec.begin(), b.vec.end(), vec.begin());
            pl cur(MAXN, -1);

            // All items are now in sorted order, relative to first key.
            // mn and max represent the range of indices 
            FD(i, ll(vec.size())-1, -1) indices[i] = cur = merge(pair(vec[i].V, vec[i].V), cur);
        }
    };

    node tr[2*MAXN];

    pair<int, pl> query(int l, int r, int x){
        int cnt=0;
        pl res(MAXN, -1);

        auto handle = [&](node& cur) {
            auto &[vec, indices] = cur;
            auto itr = lower_bound(A(vec), pair(x, -1));
            int pos = (int)(itr - vec.begin());
            cnt += (int)(vec.end() - itr);
            if(itr!=vec.end()) res = merge(res, indices[pos]);
        };

        for(l+=MAXN, r+=MAXN; l<r; l>>=1, r>>=1){
            if(l&1) handle(tr[l++]);
            if(r&1) handle(tr[--r]);
        }

        return {cnt, res};
    }

    void build(vl res) {
        F(i, 0, res.size()) seg::tr[MAXN+i]=seg::node(res[i], i);
        FD(i, MAXN-1, -1) tr[i]=node(tr[i<<1], tr[i<<1|1]);
    }
}
 
 
int arr[MAXN];
 
void init(int n, vector<int> H) {
    vl maxl(n), maxr(n);
    copy(A(H), arr);

    spmin = SparseTable<ll>(H, [](ll a, ll b) {
        return min(a, b);
    }, INF);

    F(i, 0, n) {
        int x;
        for(x=i-1; x!=-1 && H[x]<H[i]; x=maxl[x]);
        maxl[i]=x;
    }

    FD(i, n-1, -1) {
        int x;
        for(x=i+1; x!=n && H[x]<H[i]; x=maxr[x]);
        maxr[i]=x;
    }
    // maxl and maxr finds closest node greater than it to left and right ? not sure 

    vl res(n);

    F(i, 0, n) {
        int l = maxl[i], r = maxr[i];
        // H[i] is trying to glue the left and right, so it must take the max of 
        // the two valleys to either side.
        res[i] = H[i] - max(spmin.query(l+1, i), spmin.query(i+1, r));
    }

    seg::build(res);
}
 
int max_towers(int L, int R, int D) {
    // Queries in the range [l, r] for all res values (peaks with glue value) >= D, and then returns 
    // how many items were in the range, the minimum indexed peak, and maximum indexed peak of said range.
    auto [cnt, indices] = seg::query(L, R+1, D);
    if(!cnt) return 1;
    auto [mn, mx] = indices;

    // we want to find something to lease to the left and right
    // since we're only counting peaks (we actually lease valleys)
    // we would like to lease (cnt+1) things since (cnt+1) gaps,
    // but need to make sure endpoints are legit

    bool sa = (D > arr[mn] - spmin.query(L, mn));
    bool sb = (D > arr[mx] - spmin.query(mx+1, R+1));

    return max(1, (cnt + 1) - sa - sb);
}

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	323 ms	36908 KB	Output is correct
2	Correct	683 ms	55748 KB	Output is correct
3	Correct	674 ms	55848 KB	Output is correct
4	Correct	643 ms	55824 KB	Output is correct
5	Correct	630 ms	55768 KB	Output is correct
6	Correct	634 ms	55888 KB	Output is correct
7	Correct	600 ms	55752 KB	Output is correct
8	Correct	4 ms	9816 KB	Output is correct
9	Correct	4 ms	10840 KB	Output is correct
10	Correct	6 ms	10812 KB	Output is correct

Subtask #2
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	10072 KB	Output is correct
2	Correct	5 ms	10840 KB	Output is correct
3	Correct	4 ms	10840 KB	Output is correct
4	Correct	4 ms	10840 KB	Output is correct
5	Correct	4 ms	10840 KB	Output is correct
6	Correct	4 ms	10840 KB	Output is correct
7	Correct	4 ms	10840 KB	Output is correct
8	Correct	4 ms	10840 KB	Output is correct
9	Correct	4 ms	10836 KB	Output is correct
10	Correct	4 ms	10840 KB	Output is correct
11	Correct	4 ms	10840 KB	Output is correct
12	Correct	4 ms	9816 KB	Output is correct
13	Correct	4 ms	10840 KB	Output is correct
14	Correct	4 ms	10908 KB	Output is correct
15	Correct	4 ms	10840 KB	Output is correct
16	Correct	4 ms	10840 KB	Output is correct
17	Correct	5 ms	10840 KB	Output is correct
18	Correct	4 ms	10840 KB	Output is correct
19	Correct	4 ms	10840 KB	Output is correct
20	Correct	4 ms	10840 KB	Output is correct
21	Correct	4 ms	10840 KB	Output is correct
22	Correct	4 ms	10840 KB	Output is correct
23	Correct	5 ms	10840 KB	Output is correct
24	Correct	4 ms	10840 KB	Output is correct
25	Correct	4 ms	10328 KB	Output is correct
26	Correct	4 ms	10840 KB	Output is correct
27	Correct	5 ms	10840 KB	Output is correct
28	Correct	4 ms	10840 KB	Output is correct
29	Correct	4 ms	10840 KB	Output is correct
30	Correct	5 ms	11096 KB	Output is correct
31	Correct	5 ms	10840 KB	Output is correct
32	Correct	4 ms	10840 KB	Output is correct
33	Correct	4 ms	10840 KB	Output is correct
34	Correct	4 ms	10908 KB	Output is correct
35	Correct	4 ms	10840 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	10072 KB	Output is correct
2	Correct	5 ms	10840 KB	Output is correct
3	Correct	4 ms	10840 KB	Output is correct
4	Correct	4 ms	10840 KB	Output is correct
5	Correct	4 ms	10840 KB	Output is correct
6	Correct	4 ms	10840 KB	Output is correct
7	Correct	4 ms	10840 KB	Output is correct
8	Correct	4 ms	10840 KB	Output is correct
9	Correct	4 ms	10836 KB	Output is correct
10	Correct	4 ms	10840 KB	Output is correct
11	Correct	4 ms	10840 KB	Output is correct
12	Correct	4 ms	9816 KB	Output is correct
13	Correct	4 ms	10840 KB	Output is correct
14	Correct	4 ms	10908 KB	Output is correct
15	Correct	4 ms	10840 KB	Output is correct
16	Correct	4 ms	10840 KB	Output is correct
17	Correct	5 ms	10840 KB	Output is correct
18	Correct	4 ms	10840 KB	Output is correct
19	Correct	4 ms	10840 KB	Output is correct
20	Correct	4 ms	10840 KB	Output is correct
21	Correct	4 ms	10840 KB	Output is correct
22	Correct	4 ms	10840 KB	Output is correct
23	Correct	5 ms	10840 KB	Output is correct
24	Correct	4 ms	10840 KB	Output is correct
25	Correct	4 ms	10328 KB	Output is correct
26	Correct	4 ms	10840 KB	Output is correct
27	Correct	5 ms	10840 KB	Output is correct
28	Correct	4 ms	10840 KB	Output is correct
29	Correct	4 ms	10840 KB	Output is correct
30	Correct	5 ms	11096 KB	Output is correct
31	Correct	5 ms	10840 KB	Output is correct
32	Correct	4 ms	10840 KB	Output is correct
33	Correct	4 ms	10840 KB	Output is correct
34	Correct	4 ms	10908 KB	Output is correct
35	Correct	4 ms	10840 KB	Output is correct
36	Correct	46 ms	39420 KB	Output is correct
37	Correct	69 ms	55764 KB	Output is correct
38	Correct	69 ms	55864 KB	Output is correct
39	Correct	66 ms	56092 KB	Output is correct
40	Correct	66 ms	55808 KB	Output is correct
41	Correct	68 ms	55740 KB	Output is correct
42	Correct	67 ms	55856 KB	Output is correct
43	Correct	59 ms	55756 KB	Output is correct
44	Correct	60 ms	55888 KB	Output is correct
45	Correct	61 ms	55888 KB	Output is correct
46	Correct	59 ms	55760 KB	Output is correct
47	Correct	68 ms	55748 KB	Output is correct
48	Correct	68 ms	55888 KB	Output is correct
49	Correct	67 ms	55856 KB	Output is correct
50	Correct	60 ms	55756 KB	Output is correct
51	Correct	63 ms	55888 KB	Output is correct
52	Correct	68 ms	55752 KB	Output is correct
53	Correct	66 ms	55708 KB	Output is correct
54	Correct	65 ms	55760 KB	Output is correct
55	Correct	60 ms	55760 KB	Output is correct
56	Correct	61 ms	55760 KB	Output is correct
57	Correct	72 ms	54088 KB	Output is correct
58	Correct	68 ms	55728 KB	Output is correct
59	Correct	73 ms	55740 KB	Output is correct
60	Correct	66 ms	55740 KB	Output is correct
61	Correct	66 ms	55656 KB	Output is correct
62	Correct	66 ms	55776 KB	Output is correct
63	Correct	66 ms	55828 KB	Output is correct
64	Correct	60 ms	55880 KB	Output is correct
65	Correct	60 ms	55764 KB	Output is correct
66	Correct	65 ms	56024 KB	Output is correct
67	Correct	59 ms	55848 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	558 ms	55336 KB	Output is correct
2	Correct	710 ms	55888 KB	Output is correct
3	Correct	720 ms	55752 KB	Output is correct
4	Correct	683 ms	55760 KB	Output is correct
5	Correct	703 ms	55752 KB	Output is correct
6	Correct	682 ms	55768 KB	Output is correct
7	Correct	686 ms	55756 KB	Output is correct
8	Correct	657 ms	55756 KB	Output is correct
9	Correct	662 ms	55804 KB	Output is correct
10	Correct	660 ms	55888 KB	Output is correct
11	Correct	663 ms	55888 KB	Output is correct
12	Correct	671 ms	55752 KB	Output is correct
13	Correct	691 ms	55832 KB	Output is correct
14	Correct	3 ms	9816 KB	Output is correct
15	Correct	4 ms	10840 KB	Output is correct
16	Correct	5 ms	10840 KB	Output is correct
17	Correct	68 ms	55740 KB	Output is correct
18	Correct	69 ms	55756 KB	Output is correct
19	Correct	68 ms	55868 KB	Output is correct
20	Correct	60 ms	55736 KB	Output is correct
21	Correct	59 ms	55760 KB	Output is correct
22	Correct	69 ms	55888 KB	Output is correct
23	Correct	67 ms	55744 KB	Output is correct
24	Correct	73 ms	55756 KB	Output is correct
25	Correct	59 ms	55820 KB	Output is correct
26	Correct	61 ms	55740 KB	Output is correct
27	Correct	4 ms	10840 KB	Output is correct
28	Correct	4 ms	10908 KB	Output is correct
29	Correct	4 ms	10840 KB	Output is correct
30	Correct	4 ms	10840 KB	Output is correct
31	Correct	5 ms	11092 KB	Output is correct
32	Correct	5 ms	10840 KB	Output is correct
33	Correct	4 ms	10908 KB	Output is correct
34	Correct	4 ms	10720 KB	Output is correct
35	Correct	5 ms	10840 KB	Output is correct
36	Correct	4 ms	10840 KB	Output is correct

Subtask #5
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	175 ms	20584 KB	Output is correct
2	Correct	694 ms	55740 KB	Output is correct
3	Correct	674 ms	55760 KB	Output is correct
4	Correct	662 ms	55760 KB	Output is correct
5	Correct	669 ms	55776 KB	Output is correct
6	Correct	660 ms	55756 KB	Output is correct
7	Correct	651 ms	55720 KB	Output is correct
8	Correct	577 ms	55816 KB	Output is correct
9	Correct	570 ms	55736 KB	Output is correct
10	Correct	571 ms	55760 KB	Output is correct
11	Correct	600 ms	55756 KB	Output is correct
12	Correct	65 ms	55848 KB	Output is correct
13	Correct	69 ms	55764 KB	Output is correct
14	Correct	67 ms	55696 KB	Output is correct
15	Correct	58 ms	55888 KB	Output is correct
16	Correct	60 ms	55888 KB	Output is correct
17	Correct	71 ms	54260 KB	Output is correct
18	Correct	67 ms	55764 KB	Output is correct
19	Correct	69 ms	55752 KB	Output is correct
20	Correct	70 ms	55756 KB	Output is correct
21	Correct	68 ms	55804 KB	Output is correct
22	Correct	66 ms	55888 KB	Output is correct
23	Correct	70 ms	55888 KB	Output is correct
24	Correct	59 ms	55740 KB	Output is correct
25	Correct	61 ms	55736 KB	Output is correct
26	Correct	59 ms	56140 KB	Output is correct
27	Correct	60 ms	55884 KB	Output is correct
28	Correct	5 ms	10836 KB	Output is correct
29	Correct	5 ms	10840 KB	Output is correct
30	Correct	5 ms	10840 KB	Output is correct
31	Correct	5 ms	10852 KB	Output is correct
32	Correct	4 ms	10840 KB	Output is correct
33	Correct	4 ms	10328 KB	Output is correct
34	Correct	5 ms	10840 KB	Output is correct
35	Correct	5 ms	10840 KB	Output is correct
36	Correct	5 ms	10840 KB	Output is correct
37	Correct	7 ms	10840 KB	Output is correct
38	Correct	5 ms	10840 KB	Output is correct
39	Correct	5 ms	10840 KB	Output is correct
40	Correct	5 ms	10840 KB	Output is correct
41	Correct	5 ms	11160 KB	Output is correct
42	Correct	5 ms	10840 KB	Output is correct
43	Correct	5 ms	10820 KB	Output is correct

Subtask #6
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	10072 KB	Output is correct
2	Correct	5 ms	10840 KB	Output is correct
3	Correct	4 ms	10840 KB	Output is correct
4	Correct	4 ms	10840 KB	Output is correct
5	Correct	4 ms	10840 KB	Output is correct
6	Correct	4 ms	10840 KB	Output is correct
7	Correct	4 ms	10840 KB	Output is correct
8	Correct	4 ms	10840 KB	Output is correct
9	Correct	4 ms	10836 KB	Output is correct
10	Correct	4 ms	10840 KB	Output is correct
11	Correct	4 ms	10840 KB	Output is correct
12	Correct	4 ms	9816 KB	Output is correct
13	Correct	4 ms	10840 KB	Output is correct
14	Correct	4 ms	10908 KB	Output is correct
15	Correct	4 ms	10840 KB	Output is correct
16	Correct	4 ms	10840 KB	Output is correct
17	Correct	5 ms	10840 KB	Output is correct
18	Correct	4 ms	10840 KB	Output is correct
19	Correct	4 ms	10840 KB	Output is correct
20	Correct	4 ms	10840 KB	Output is correct
21	Correct	4 ms	10840 KB	Output is correct
22	Correct	4 ms	10840 KB	Output is correct
23	Correct	5 ms	10840 KB	Output is correct
24	Correct	4 ms	10840 KB	Output is correct
25	Correct	4 ms	10328 KB	Output is correct
26	Correct	4 ms	10840 KB	Output is correct
27	Correct	5 ms	10840 KB	Output is correct
28	Correct	4 ms	10840 KB	Output is correct
29	Correct	4 ms	10840 KB	Output is correct
30	Correct	5 ms	11096 KB	Output is correct
31	Correct	5 ms	10840 KB	Output is correct
32	Correct	4 ms	10840 KB	Output is correct
33	Correct	4 ms	10840 KB	Output is correct
34	Correct	4 ms	10908 KB	Output is correct
35	Correct	4 ms	10840 KB	Output is correct
36	Correct	46 ms	39420 KB	Output is correct
37	Correct	69 ms	55764 KB	Output is correct
38	Correct	69 ms	55864 KB	Output is correct
39	Correct	66 ms	56092 KB	Output is correct
40	Correct	66 ms	55808 KB	Output is correct
41	Correct	68 ms	55740 KB	Output is correct
42	Correct	67 ms	55856 KB	Output is correct
43	Correct	59 ms	55756 KB	Output is correct
44	Correct	60 ms	55888 KB	Output is correct
45	Correct	61 ms	55888 KB	Output is correct
46	Correct	59 ms	55760 KB	Output is correct
47	Correct	68 ms	55748 KB	Output is correct
48	Correct	68 ms	55888 KB	Output is correct
49	Correct	67 ms	55856 KB	Output is correct
50	Correct	60 ms	55756 KB	Output is correct
51	Correct	63 ms	55888 KB	Output is correct
52	Correct	68 ms	55752 KB	Output is correct
53	Correct	66 ms	55708 KB	Output is correct
54	Correct	65 ms	55760 KB	Output is correct
55	Correct	60 ms	55760 KB	Output is correct
56	Correct	61 ms	55760 KB	Output is correct
57	Correct	72 ms	54088 KB	Output is correct
58	Correct	68 ms	55728 KB	Output is correct
59	Correct	73 ms	55740 KB	Output is correct
60	Correct	66 ms	55740 KB	Output is correct
61	Correct	66 ms	55656 KB	Output is correct
62	Correct	66 ms	55776 KB	Output is correct
63	Correct	66 ms	55828 KB	Output is correct
64	Correct	60 ms	55880 KB	Output is correct
65	Correct	60 ms	55764 KB	Output is correct
66	Correct	65 ms	56024 KB	Output is correct
67	Correct	59 ms	55848 KB	Output is correct
68	Correct	558 ms	55336 KB	Output is correct
69	Correct	710 ms	55888 KB	Output is correct
70	Correct	720 ms	55752 KB	Output is correct
71	Correct	683 ms	55760 KB	Output is correct
72	Correct	703 ms	55752 KB	Output is correct
73	Correct	682 ms	55768 KB	Output is correct
74	Correct	686 ms	55756 KB	Output is correct
75	Correct	657 ms	55756 KB	Output is correct
76	Correct	662 ms	55804 KB	Output is correct
77	Correct	660 ms	55888 KB	Output is correct
78	Correct	663 ms	55888 KB	Output is correct
79	Correct	671 ms	55752 KB	Output is correct
80	Correct	691 ms	55832 KB	Output is correct
81	Correct	3 ms	9816 KB	Output is correct
82	Correct	4 ms	10840 KB	Output is correct
83	Correct	5 ms	10840 KB	Output is correct
84	Correct	68 ms	55740 KB	Output is correct
85	Correct	69 ms	55756 KB	Output is correct
86	Correct	68 ms	55868 KB	Output is correct
87	Correct	60 ms	55736 KB	Output is correct
88	Correct	59 ms	55760 KB	Output is correct
89	Correct	69 ms	55888 KB	Output is correct
90	Correct	67 ms	55744 KB	Output is correct
91	Correct	73 ms	55756 KB	Output is correct
92	Correct	59 ms	55820 KB	Output is correct
93	Correct	61 ms	55740 KB	Output is correct
94	Correct	4 ms	10840 KB	Output is correct
95	Correct	4 ms	10908 KB	Output is correct
96	Correct	4 ms	10840 KB	Output is correct
97	Correct	4 ms	10840 KB	Output is correct
98	Correct	5 ms	11092 KB	Output is correct
99	Correct	5 ms	10840 KB	Output is correct
100	Correct	4 ms	10908 KB	Output is correct
101	Correct	4 ms	10720 KB	Output is correct
102	Correct	5 ms	10840 KB	Output is correct
103	Correct	4 ms	10840 KB	Output is correct
104	Correct	685 ms	50472 KB	Output is correct
105	Correct	737 ms	55792 KB	Output is correct
106	Correct	735 ms	55736 KB	Output is correct
107	Correct	725 ms	55652 KB	Output is correct
108	Correct	712 ms	55752 KB	Output is correct
109	Correct	690 ms	55744 KB	Output is correct
110	Correct	680 ms	55760 KB	Output is correct
111	Correct	682 ms	55764 KB	Output is correct
112	Correct	695 ms	55696 KB	Output is correct
113	Correct	664 ms	55760 KB	Output is correct
114	Correct	658 ms	55760 KB	Output is correct

Subtask #7
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	323 ms	36908 KB	Output is correct
2	Correct	683 ms	55748 KB	Output is correct
3	Correct	674 ms	55848 KB	Output is correct
4	Correct	643 ms	55824 KB	Output is correct
5	Correct	630 ms	55768 KB	Output is correct
6	Correct	634 ms	55888 KB	Output is correct
7	Correct	600 ms	55752 KB	Output is correct
8	Correct	4 ms	9816 KB	Output is correct
9	Correct	4 ms	10840 KB	Output is correct
10	Correct	6 ms	10812 KB	Output is correct
11	Correct	3 ms	10072 KB	Output is correct
12	Correct	5 ms	10840 KB	Output is correct
13	Correct	4 ms	10840 KB	Output is correct
14	Correct	4 ms	10840 KB	Output is correct
15	Correct	4 ms	10840 KB	Output is correct
16	Correct	4 ms	10840 KB	Output is correct
17	Correct	4 ms	10840 KB	Output is correct
18	Correct	4 ms	10840 KB	Output is correct
19	Correct	4 ms	10836 KB	Output is correct
20	Correct	4 ms	10840 KB	Output is correct
21	Correct	4 ms	10840 KB	Output is correct
22	Correct	4 ms	9816 KB	Output is correct
23	Correct	4 ms	10840 KB	Output is correct
24	Correct	4 ms	10908 KB	Output is correct
25	Correct	4 ms	10840 KB	Output is correct
26	Correct	4 ms	10840 KB	Output is correct
27	Correct	5 ms	10840 KB	Output is correct
28	Correct	4 ms	10840 KB	Output is correct
29	Correct	4 ms	10840 KB	Output is correct
30	Correct	4 ms	10840 KB	Output is correct
31	Correct	4 ms	10840 KB	Output is correct
32	Correct	4 ms	10840 KB	Output is correct
33	Correct	5 ms	10840 KB	Output is correct
34	Correct	4 ms	10840 KB	Output is correct
35	Correct	4 ms	10328 KB	Output is correct
36	Correct	4 ms	10840 KB	Output is correct
37	Correct	5 ms	10840 KB	Output is correct
38	Correct	4 ms	10840 KB	Output is correct
39	Correct	4 ms	10840 KB	Output is correct
40	Correct	5 ms	11096 KB	Output is correct
41	Correct	5 ms	10840 KB	Output is correct
42	Correct	4 ms	10840 KB	Output is correct
43	Correct	4 ms	10840 KB	Output is correct
44	Correct	4 ms	10908 KB	Output is correct
45	Correct	4 ms	10840 KB	Output is correct
46	Correct	46 ms	39420 KB	Output is correct
47	Correct	69 ms	55764 KB	Output is correct
48	Correct	69 ms	55864 KB	Output is correct
49	Correct	66 ms	56092 KB	Output is correct
50	Correct	66 ms	55808 KB	Output is correct
51	Correct	68 ms	55740 KB	Output is correct
52	Correct	67 ms	55856 KB	Output is correct
53	Correct	59 ms	55756 KB	Output is correct
54	Correct	60 ms	55888 KB	Output is correct
55	Correct	61 ms	55888 KB	Output is correct
56	Correct	59 ms	55760 KB	Output is correct
57	Correct	68 ms	55748 KB	Output is correct
58	Correct	68 ms	55888 KB	Output is correct
59	Correct	67 ms	55856 KB	Output is correct
60	Correct	60 ms	55756 KB	Output is correct
61	Correct	63 ms	55888 KB	Output is correct
62	Correct	68 ms	55752 KB	Output is correct
63	Correct	66 ms	55708 KB	Output is correct
64	Correct	65 ms	55760 KB	Output is correct
65	Correct	60 ms	55760 KB	Output is correct
66	Correct	61 ms	55760 KB	Output is correct
67	Correct	72 ms	54088 KB	Output is correct
68	Correct	68 ms	55728 KB	Output is correct
69	Correct	73 ms	55740 KB	Output is correct
70	Correct	66 ms	55740 KB	Output is correct
71	Correct	66 ms	55656 KB	Output is correct
72	Correct	66 ms	55776 KB	Output is correct
73	Correct	66 ms	55828 KB	Output is correct
74	Correct	60 ms	55880 KB	Output is correct
75	Correct	60 ms	55764 KB	Output is correct
76	Correct	65 ms	56024 KB	Output is correct
77	Correct	59 ms	55848 KB	Output is correct
78	Correct	558 ms	55336 KB	Output is correct
79	Correct	710 ms	55888 KB	Output is correct
80	Correct	720 ms	55752 KB	Output is correct
81	Correct	683 ms	55760 KB	Output is correct
82	Correct	703 ms	55752 KB	Output is correct
83	Correct	682 ms	55768 KB	Output is correct
84	Correct	686 ms	55756 KB	Output is correct
85	Correct	657 ms	55756 KB	Output is correct
86	Correct	662 ms	55804 KB	Output is correct
87	Correct	660 ms	55888 KB	Output is correct
88	Correct	663 ms	55888 KB	Output is correct
89	Correct	671 ms	55752 KB	Output is correct
90	Correct	691 ms	55832 KB	Output is correct
91	Correct	3 ms	9816 KB	Output is correct
92	Correct	4 ms	10840 KB	Output is correct
93	Correct	5 ms	10840 KB	Output is correct
94	Correct	68 ms	55740 KB	Output is correct
95	Correct	69 ms	55756 KB	Output is correct
96	Correct	68 ms	55868 KB	Output is correct
97	Correct	60 ms	55736 KB	Output is correct
98	Correct	59 ms	55760 KB	Output is correct
99	Correct	69 ms	55888 KB	Output is correct
100	Correct	67 ms	55744 KB	Output is correct
101	Correct	73 ms	55756 KB	Output is correct
102	Correct	59 ms	55820 KB	Output is correct
103	Correct	61 ms	55740 KB	Output is correct
104	Correct	4 ms	10840 KB	Output is correct
105	Correct	4 ms	10908 KB	Output is correct
106	Correct	4 ms	10840 KB	Output is correct
107	Correct	4 ms	10840 KB	Output is correct
108	Correct	5 ms	11092 KB	Output is correct
109	Correct	5 ms	10840 KB	Output is correct
110	Correct	4 ms	10908 KB	Output is correct
111	Correct	4 ms	10720 KB	Output is correct
112	Correct	5 ms	10840 KB	Output is correct
113	Correct	4 ms	10840 KB	Output is correct
114	Correct	175 ms	20584 KB	Output is correct
115	Correct	694 ms	55740 KB	Output is correct
116	Correct	674 ms	55760 KB	Output is correct
117	Correct	662 ms	55760 KB	Output is correct
118	Correct	669 ms	55776 KB	Output is correct
119	Correct	660 ms	55756 KB	Output is correct
120	Correct	651 ms	55720 KB	Output is correct
121	Correct	577 ms	55816 KB	Output is correct
122	Correct	570 ms	55736 KB	Output is correct
123	Correct	571 ms	55760 KB	Output is correct
124	Correct	600 ms	55756 KB	Output is correct
125	Correct	65 ms	55848 KB	Output is correct
126	Correct	69 ms	55764 KB	Output is correct
127	Correct	67 ms	55696 KB	Output is correct
128	Correct	58 ms	55888 KB	Output is correct
129	Correct	60 ms	55888 KB	Output is correct
130	Correct	71 ms	54260 KB	Output is correct
131	Correct	67 ms	55764 KB	Output is correct
132	Correct	69 ms	55752 KB	Output is correct
133	Correct	70 ms	55756 KB	Output is correct
134	Correct	68 ms	55804 KB	Output is correct
135	Correct	66 ms	55888 KB	Output is correct
136	Correct	70 ms	55888 KB	Output is correct
137	Correct	59 ms	55740 KB	Output is correct
138	Correct	61 ms	55736 KB	Output is correct
139	Correct	59 ms	56140 KB	Output is correct
140	Correct	60 ms	55884 KB	Output is correct
141	Correct	5 ms	10836 KB	Output is correct
142	Correct	5 ms	10840 KB	Output is correct
143	Correct	5 ms	10840 KB	Output is correct
144	Correct	5 ms	10852 KB	Output is correct
145	Correct	4 ms	10840 KB	Output is correct
146	Correct	4 ms	10328 KB	Output is correct
147	Correct	5 ms	10840 KB	Output is correct
148	Correct	5 ms	10840 KB	Output is correct
149	Correct	5 ms	10840 KB	Output is correct
150	Correct	7 ms	10840 KB	Output is correct
151	Correct	5 ms	10840 KB	Output is correct
152	Correct	5 ms	10840 KB	Output is correct
153	Correct	5 ms	10840 KB	Output is correct
154	Correct	5 ms	11160 KB	Output is correct
155	Correct	5 ms	10840 KB	Output is correct
156	Correct	5 ms	10820 KB	Output is correct
157	Correct	685 ms	50472 KB	Output is correct
158	Correct	737 ms	55792 KB	Output is correct
159	Correct	735 ms	55736 KB	Output is correct
160	Correct	725 ms	55652 KB	Output is correct
161	Correct	712 ms	55752 KB	Output is correct
162	Correct	690 ms	55744 KB	Output is correct
163	Correct	680 ms	55760 KB	Output is correct
164	Correct	682 ms	55764 KB	Output is correct
165	Correct	695 ms	55696 KB	Output is correct
166	Correct	664 ms	55760 KB	Output is correct
167	Correct	658 ms	55760 KB	Output is correct
168	Correct	4 ms	9816 KB	Output is correct
169	Correct	464 ms	25324 KB	Output is correct
170	Correct	759 ms	55756 KB	Output is correct
171	Correct	789 ms	55740 KB	Output is correct
172	Correct	852 ms	55756 KB	Output is correct
173	Correct	829 ms	55888 KB	Output is correct
174	Correct	846 ms	55888 KB	Output is correct
175	Correct	895 ms	55888 KB	Output is correct
176	Correct	658 ms	55744 KB	Output is correct
177	Correct	735 ms	55756 KB	Output is correct
178	Correct	663 ms	55656 KB	Output is correct
179	Correct	720 ms	56272 KB	Output is correct

답안 #914860

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 11.0 / 11.0

Subtask #3 12.0 / 12.0

Subtask #4 14.0 / 14.0

Subtask #5 17.0 / 17.0

Subtask #6 19.0 / 19.0

Subtask #7 23.0 / 23.0

Subtask #1
4.0 / 4.0

Subtask #2
11.0 / 11.0

Subtask #3
12.0 / 12.0

Subtask #4
14.0 / 14.0

Subtask #5
17.0 / 17.0

Subtask #6
19.0 / 19.0

Subtask #7
23.0 / 23.0