답안 #914867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
914867	2024-01-22T19:26:12 Z	bobbilyking	송신탑 (IOI22_towers)	C++17	100 / 100	812 ms	56000 KB

towers

/*

step 1. we really only care about peaks and valleys of the array
step 2. once we have the list of peaks, precompute the valleys to the left and right of each peak. The "glue value" of the peak is Height[peak] - max(Height[left valley], Height[right valley]), which the maximum D value allowed s.t. this peak can be the transmission tower between the two adjacent valleys

Step 3. Put these peaks in a 2d segtree, represetning (position, value, original index in array). This segtree needs to be able to support:

    // 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.

Step 4. The answer is simply doing the above query, this gets us the # of peaks, then do some fixing on the endpoints to make sure that the left and right endpoints are valid valleys or not.

Proof of why this works:

Intuitively, what the final construction is doing is using the peaks as "glue" values for the valleys and then verifying that all gaps work. 

The construction works as a lower bound, since by definition of how we put things into the segtree, the valleys on both sides are valid to select (except as an endpoint). Even if we skip peaks, if two peaks satisfy the >=D property, one of the valleys on both sides must satisfy it. 

(WLOG, Let's say H[peak_l] < H[peak_r], and both are selected. This means that H[right_valley[peak_l]] is a valid transition point).

So all glue points work, we can select a valley between any of them. We just need to take care about the valleys on the endpoints, but that is an easy fix. 

To show this is an upper bound: (SKETCH)

First recall that only peaks are useful as "glue" and valleys are useful as chosen towers (except at endpoints which we handle already).

With our segtree query, we only ever query peaks in the range with a sufficiently high glue value, so we need to show that having one of these peaks without a sufficiently high glue value will never work.

Well, that's easy: "insufficient glue value" means that we can't pick both of the adjacent valleys in our answer; we can only pick one of them. But if we can only pick one of them, then there's no point in using this peak as a glue value. So our query is correct in not picking this peak as a glue value.

What about the endpoints: Notice that the endpoints can only make not-valleys seem like valleys, i.e. shrink the effective D value, so we're only ever selecting a potentially incorrect glue value, and fixing it afterwards; we never miss a candidate solution. 

====================================================================================================================

	[ a bit confusing argument down below] 

	- Formally, you'd first make the claim that glue towers must be peaks; this can be shown fairly easily. Then, you use an exchange argument: The two valleys adjacent to a useless peak can't be selected, so we must select only one of them. Like this
	
	Originally, we have
	
	P V (useless peak) V P 
	
	First, (useless peak) cannot join the two V's by definition. So we can't select both V's. So we only select one of them. WLOG select the left V.
	
	P V | (useless peak) _ P
	
	If we selected P as glue in our query, that means height(P) > height(useless peak), since the useless valley contributed to both of their precomps.  
	
	If we didn't, you can probably propogate the value until we actually select a glue P and gg.

The "fixing" side is hard to express here but it should be clear in the code
*/

#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	308 ms	36952 KB	Output is correct
2	Correct	688 ms	55752 KB	Output is correct
3	Correct	678 ms	55760 KB	Output is correct
4	Correct	625 ms	55760 KB	Output is correct
5	Correct	646 ms	55888 KB	Output is correct
6	Correct	641 ms	55888 KB	Output is correct
7	Correct	610 ms	55756 KB	Output is correct
8	Correct	3 ms	9816 KB	Output is correct
9	Correct	4 ms	10840 KB	Output is correct
10	Correct	4 ms	10824 KB	Output is correct

Subtask #2
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	10072 KB	Output is correct
2	Correct	5 ms	10840 KB	Output is correct
3	Correct	5 ms	10840 KB	Output is correct
4	Correct	4 ms	10840 KB	Output is correct
5	Correct	5 ms	10840 KB	Output is correct
6	Correct	5 ms	10840 KB	Output is correct
7	Correct	4 ms	10840 KB	Output is correct
8	Correct	5 ms	10840 KB	Output is correct
9	Correct	4 ms	10840 KB	Output is correct
10	Correct	4 ms	10840 KB	Output is correct
11	Correct	4 ms	10840 KB	Output is correct
12	Correct	3 ms	9904 KB	Output is correct
13	Correct	6 ms	11096 KB	Output is correct
14	Correct	4 ms	10872 KB	Output is correct
15	Correct	6 ms	10840 KB	Output is correct
16	Correct	5 ms	10820 KB	Output is correct
17	Correct	4 ms	10840 KB	Output is correct
18	Correct	6 ms	10816 KB	Output is correct
19	Correct	5 ms	10840 KB	Output is correct
20	Correct	4 ms	10880 KB	Output is correct
21	Correct	5 ms	10840 KB	Output is correct
22	Correct	5 ms	10892 KB	Output is correct
23	Correct	5 ms	10840 KB	Output is correct
24	Correct	5 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	10908 KB	Output is correct
28	Correct	5 ms	10840 KB	Output is correct
29	Correct	4 ms	10744 KB	Output is correct
30	Correct	5 ms	11036 KB	Output is correct
31	Correct	5 ms	10840 KB	Output is correct
32	Correct	5 ms	10840 KB	Output is correct
33	Correct	4 ms	10840 KB	Output is correct
34	Correct	4 ms	10840 KB	Output is correct
35	Correct	4 ms	10852 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	10072 KB	Output is correct
2	Correct	5 ms	10840 KB	Output is correct
3	Correct	5 ms	10840 KB	Output is correct
4	Correct	4 ms	10840 KB	Output is correct
5	Correct	5 ms	10840 KB	Output is correct
6	Correct	5 ms	10840 KB	Output is correct
7	Correct	4 ms	10840 KB	Output is correct
8	Correct	5 ms	10840 KB	Output is correct
9	Correct	4 ms	10840 KB	Output is correct
10	Correct	4 ms	10840 KB	Output is correct
11	Correct	4 ms	10840 KB	Output is correct
12	Correct	3 ms	9904 KB	Output is correct
13	Correct	6 ms	11096 KB	Output is correct
14	Correct	4 ms	10872 KB	Output is correct
15	Correct	6 ms	10840 KB	Output is correct
16	Correct	5 ms	10820 KB	Output is correct
17	Correct	4 ms	10840 KB	Output is correct
18	Correct	6 ms	10816 KB	Output is correct
19	Correct	5 ms	10840 KB	Output is correct
20	Correct	4 ms	10880 KB	Output is correct
21	Correct	5 ms	10840 KB	Output is correct
22	Correct	5 ms	10892 KB	Output is correct
23	Correct	5 ms	10840 KB	Output is correct
24	Correct	5 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	10908 KB	Output is correct
28	Correct	5 ms	10840 KB	Output is correct
29	Correct	4 ms	10744 KB	Output is correct
30	Correct	5 ms	11036 KB	Output is correct
31	Correct	5 ms	10840 KB	Output is correct
32	Correct	5 ms	10840 KB	Output is correct
33	Correct	4 ms	10840 KB	Output is correct
34	Correct	4 ms	10840 KB	Output is correct
35	Correct	4 ms	10852 KB	Output is correct
36	Correct	45 ms	39504 KB	Output is correct
37	Correct	72 ms	55732 KB	Output is correct
38	Correct	67 ms	55788 KB	Output is correct
39	Correct	65 ms	55760 KB	Output is correct
40	Correct	67 ms	55752 KB	Output is correct
41	Correct	66 ms	55740 KB	Output is correct
42	Correct	64 ms	55784 KB	Output is correct
43	Correct	57 ms	55828 KB	Output is correct
44	Correct	58 ms	55768 KB	Output is correct
45	Correct	57 ms	55808 KB	Output is correct
46	Correct	59 ms	55888 KB	Output is correct
47	Correct	64 ms	55736 KB	Output is correct
48	Correct	63 ms	55856 KB	Output is correct
49	Correct	63 ms	55904 KB	Output is correct
50	Correct	57 ms	55760 KB	Output is correct
51	Correct	58 ms	55756 KB	Output is correct
52	Correct	74 ms	55964 KB	Output is correct
53	Correct	64 ms	55888 KB	Output is correct
54	Correct	64 ms	55868 KB	Output is correct
55	Correct	58 ms	55848 KB	Output is correct
56	Correct	57 ms	55888 KB	Output is correct
57	Correct	67 ms	54352 KB	Output is correct
58	Correct	68 ms	55744 KB	Output is correct
59	Correct	64 ms	55892 KB	Output is correct
60	Correct	64 ms	55756 KB	Output is correct
61	Correct	63 ms	55656 KB	Output is correct
62	Correct	63 ms	55988 KB	Output is correct
63	Correct	64 ms	55756 KB	Output is correct
64	Correct	58 ms	55736 KB	Output is correct
65	Correct	58 ms	55712 KB	Output is correct
66	Correct	57 ms	55736 KB	Output is correct
67	Correct	56 ms	55888 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	558 ms	55480 KB	Output is correct
2	Correct	780 ms	55720 KB	Output is correct
3	Correct	758 ms	55772 KB	Output is correct
4	Correct	704 ms	55752 KB	Output is correct
5	Correct	710 ms	55880 KB	Output is correct
6	Correct	681 ms	55744 KB	Output is correct
7	Correct	672 ms	55756 KB	Output is correct
8	Correct	686 ms	55884 KB	Output is correct
9	Correct	652 ms	55764 KB	Output is correct
10	Correct	693 ms	55760 KB	Output is correct
11	Correct	710 ms	55772 KB	Output is correct
12	Correct	659 ms	55756 KB	Output is correct
13	Correct	637 ms	55856 KB	Output is correct
14	Correct	4 ms	9816 KB	Output is correct
15	Correct	5 ms	10840 KB	Output is correct
16	Correct	4 ms	10840 KB	Output is correct
17	Correct	65 ms	55744 KB	Output is correct
18	Correct	65 ms	56000 KB	Output is correct
19	Correct	63 ms	55812 KB	Output is correct
20	Correct	57 ms	55736 KB	Output is correct
21	Correct	59 ms	55748 KB	Output is correct
22	Correct	65 ms	55804 KB	Output is correct
23	Correct	64 ms	55692 KB	Output is correct
24	Correct	65 ms	55756 KB	Output is correct
25	Correct	59 ms	55744 KB	Output is correct
26	Correct	58 ms	55888 KB	Output is correct
27	Correct	7 ms	11252 KB	Output is correct
28	Correct	4 ms	10840 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	10840 KB	Output is correct
32	Correct	5 ms	10840 KB	Output is correct
33	Correct	5 ms	10840 KB	Output is correct
34	Correct	5 ms	10840 KB	Output is correct
35	Correct	5 ms	10840 KB	Output is correct
36	Correct	4 ms	10672 KB	Output is correct

Subtask #5
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	190 ms	20576 KB	Output is correct
2	Correct	688 ms	55756 KB	Output is correct
3	Correct	691 ms	55852 KB	Output is correct
4	Correct	669 ms	55736 KB	Output is correct
5	Correct	723 ms	55756 KB	Output is correct
6	Correct	662 ms	55756 KB	Output is correct
7	Correct	661 ms	55752 KB	Output is correct
8	Correct	641 ms	55752 KB	Output is correct
9	Correct	597 ms	55736 KB	Output is correct
10	Correct	611 ms	55760 KB	Output is correct
11	Correct	572 ms	55888 KB	Output is correct
12	Correct	65 ms	55876 KB	Output is correct
13	Correct	65 ms	55888 KB	Output is correct
14	Correct	63 ms	55756 KB	Output is correct
15	Correct	56 ms	55756 KB	Output is correct
16	Correct	59 ms	55888 KB	Output is correct
17	Correct	65 ms	54328 KB	Output is correct
18	Correct	64 ms	55888 KB	Output is correct
19	Correct	63 ms	55892 KB	Output is correct
20	Correct	63 ms	55740 KB	Output is correct
21	Correct	62 ms	55888 KB	Output is correct
22	Correct	64 ms	55780 KB	Output is correct
23	Correct	67 ms	55836 KB	Output is correct
24	Correct	58 ms	55856 KB	Output is correct
25	Correct	56 ms	55652 KB	Output is correct
26	Correct	57 ms	55748 KB	Output is correct
27	Correct	57 ms	55888 KB	Output is correct
28	Correct	4 ms	10840 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	10840 KB	Output is correct
32	Correct	4 ms	10840 KB	Output is correct
33	Correct	4 ms	10328 KB	Output is correct
34	Correct	4 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	5 ms	10840 KB	Output is correct
38	Correct	5 ms	10840 KB	Output is correct
39	Correct	5 ms	10836 KB	Output is correct
40	Correct	5 ms	10840 KB	Output is correct
41	Correct	4 ms	11096 KB	Output is correct
42	Correct	5 ms	10840 KB	Output is correct
43	Correct	5 ms	10840 KB	Output is correct

Subtask #6
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	10072 KB	Output is correct
2	Correct	5 ms	10840 KB	Output is correct
3	Correct	5 ms	10840 KB	Output is correct
4	Correct	4 ms	10840 KB	Output is correct
5	Correct	5 ms	10840 KB	Output is correct
6	Correct	5 ms	10840 KB	Output is correct
7	Correct	4 ms	10840 KB	Output is correct
8	Correct	5 ms	10840 KB	Output is correct
9	Correct	4 ms	10840 KB	Output is correct
10	Correct	4 ms	10840 KB	Output is correct
11	Correct	4 ms	10840 KB	Output is correct
12	Correct	3 ms	9904 KB	Output is correct
13	Correct	6 ms	11096 KB	Output is correct
14	Correct	4 ms	10872 KB	Output is correct
15	Correct	6 ms	10840 KB	Output is correct
16	Correct	5 ms	10820 KB	Output is correct
17	Correct	4 ms	10840 KB	Output is correct
18	Correct	6 ms	10816 KB	Output is correct
19	Correct	5 ms	10840 KB	Output is correct
20	Correct	4 ms	10880 KB	Output is correct
21	Correct	5 ms	10840 KB	Output is correct
22	Correct	5 ms	10892 KB	Output is correct
23	Correct	5 ms	10840 KB	Output is correct
24	Correct	5 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	10908 KB	Output is correct
28	Correct	5 ms	10840 KB	Output is correct
29	Correct	4 ms	10744 KB	Output is correct
30	Correct	5 ms	11036 KB	Output is correct
31	Correct	5 ms	10840 KB	Output is correct
32	Correct	5 ms	10840 KB	Output is correct
33	Correct	4 ms	10840 KB	Output is correct
34	Correct	4 ms	10840 KB	Output is correct
35	Correct	4 ms	10852 KB	Output is correct
36	Correct	45 ms	39504 KB	Output is correct
37	Correct	72 ms	55732 KB	Output is correct
38	Correct	67 ms	55788 KB	Output is correct
39	Correct	65 ms	55760 KB	Output is correct
40	Correct	67 ms	55752 KB	Output is correct
41	Correct	66 ms	55740 KB	Output is correct
42	Correct	64 ms	55784 KB	Output is correct
43	Correct	57 ms	55828 KB	Output is correct
44	Correct	58 ms	55768 KB	Output is correct
45	Correct	57 ms	55808 KB	Output is correct
46	Correct	59 ms	55888 KB	Output is correct
47	Correct	64 ms	55736 KB	Output is correct
48	Correct	63 ms	55856 KB	Output is correct
49	Correct	63 ms	55904 KB	Output is correct
50	Correct	57 ms	55760 KB	Output is correct
51	Correct	58 ms	55756 KB	Output is correct
52	Correct	74 ms	55964 KB	Output is correct
53	Correct	64 ms	55888 KB	Output is correct
54	Correct	64 ms	55868 KB	Output is correct
55	Correct	58 ms	55848 KB	Output is correct
56	Correct	57 ms	55888 KB	Output is correct
57	Correct	67 ms	54352 KB	Output is correct
58	Correct	68 ms	55744 KB	Output is correct
59	Correct	64 ms	55892 KB	Output is correct
60	Correct	64 ms	55756 KB	Output is correct
61	Correct	63 ms	55656 KB	Output is correct
62	Correct	63 ms	55988 KB	Output is correct
63	Correct	64 ms	55756 KB	Output is correct
64	Correct	58 ms	55736 KB	Output is correct
65	Correct	58 ms	55712 KB	Output is correct
66	Correct	57 ms	55736 KB	Output is correct
67	Correct	56 ms	55888 KB	Output is correct
68	Correct	558 ms	55480 KB	Output is correct
69	Correct	780 ms	55720 KB	Output is correct
70	Correct	758 ms	55772 KB	Output is correct
71	Correct	704 ms	55752 KB	Output is correct
72	Correct	710 ms	55880 KB	Output is correct
73	Correct	681 ms	55744 KB	Output is correct
74	Correct	672 ms	55756 KB	Output is correct
75	Correct	686 ms	55884 KB	Output is correct
76	Correct	652 ms	55764 KB	Output is correct
77	Correct	693 ms	55760 KB	Output is correct
78	Correct	710 ms	55772 KB	Output is correct
79	Correct	659 ms	55756 KB	Output is correct
80	Correct	637 ms	55856 KB	Output is correct
81	Correct	4 ms	9816 KB	Output is correct
82	Correct	5 ms	10840 KB	Output is correct
83	Correct	4 ms	10840 KB	Output is correct
84	Correct	65 ms	55744 KB	Output is correct
85	Correct	65 ms	56000 KB	Output is correct
86	Correct	63 ms	55812 KB	Output is correct
87	Correct	57 ms	55736 KB	Output is correct
88	Correct	59 ms	55748 KB	Output is correct
89	Correct	65 ms	55804 KB	Output is correct
90	Correct	64 ms	55692 KB	Output is correct
91	Correct	65 ms	55756 KB	Output is correct
92	Correct	59 ms	55744 KB	Output is correct
93	Correct	58 ms	55888 KB	Output is correct
94	Correct	7 ms	11252 KB	Output is correct
95	Correct	4 ms	10840 KB	Output is correct
96	Correct	5 ms	10840 KB	Output is correct
97	Correct	5 ms	10840 KB	Output is correct
98	Correct	5 ms	10840 KB	Output is correct
99	Correct	5 ms	10840 KB	Output is correct
100	Correct	5 ms	10840 KB	Output is correct
101	Correct	5 ms	10840 KB	Output is correct
102	Correct	5 ms	10840 KB	Output is correct
103	Correct	4 ms	10672 KB	Output is correct
104	Correct	693 ms	50508 KB	Output is correct
105	Correct	781 ms	55760 KB	Output is correct
106	Correct	746 ms	55740 KB	Output is correct
107	Correct	726 ms	55756 KB	Output is correct
108	Correct	692 ms	55868 KB	Output is correct
109	Correct	762 ms	55740 KB	Output is correct
110	Correct	719 ms	55736 KB	Output is correct
111	Correct	654 ms	55756 KB	Output is correct
112	Correct	729 ms	55744 KB	Output is correct
113	Correct	667 ms	55888 KB	Output is correct
114	Correct	732 ms	55680 KB	Output is correct

Subtask #7
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	308 ms	36952 KB	Output is correct
2	Correct	688 ms	55752 KB	Output is correct
3	Correct	678 ms	55760 KB	Output is correct
4	Correct	625 ms	55760 KB	Output is correct
5	Correct	646 ms	55888 KB	Output is correct
6	Correct	641 ms	55888 KB	Output is correct
7	Correct	610 ms	55756 KB	Output is correct
8	Correct	3 ms	9816 KB	Output is correct
9	Correct	4 ms	10840 KB	Output is correct
10	Correct	4 ms	10824 KB	Output is correct
11	Correct	4 ms	10072 KB	Output is correct
12	Correct	5 ms	10840 KB	Output is correct
13	Correct	5 ms	10840 KB	Output is correct
14	Correct	4 ms	10840 KB	Output is correct
15	Correct	5 ms	10840 KB	Output is correct
16	Correct	5 ms	10840 KB	Output is correct
17	Correct	4 ms	10840 KB	Output is correct
18	Correct	5 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	3 ms	9904 KB	Output is correct
23	Correct	6 ms	11096 KB	Output is correct
24	Correct	4 ms	10872 KB	Output is correct
25	Correct	6 ms	10840 KB	Output is correct
26	Correct	5 ms	10820 KB	Output is correct
27	Correct	4 ms	10840 KB	Output is correct
28	Correct	6 ms	10816 KB	Output is correct
29	Correct	5 ms	10840 KB	Output is correct
30	Correct	4 ms	10880 KB	Output is correct
31	Correct	5 ms	10840 KB	Output is correct
32	Correct	5 ms	10892 KB	Output is correct
33	Correct	5 ms	10840 KB	Output is correct
34	Correct	5 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	10908 KB	Output is correct
38	Correct	5 ms	10840 KB	Output is correct
39	Correct	4 ms	10744 KB	Output is correct
40	Correct	5 ms	11036 KB	Output is correct
41	Correct	5 ms	10840 KB	Output is correct
42	Correct	5 ms	10840 KB	Output is correct
43	Correct	4 ms	10840 KB	Output is correct
44	Correct	4 ms	10840 KB	Output is correct
45	Correct	4 ms	10852 KB	Output is correct
46	Correct	45 ms	39504 KB	Output is correct
47	Correct	72 ms	55732 KB	Output is correct
48	Correct	67 ms	55788 KB	Output is correct
49	Correct	65 ms	55760 KB	Output is correct
50	Correct	67 ms	55752 KB	Output is correct
51	Correct	66 ms	55740 KB	Output is correct
52	Correct	64 ms	55784 KB	Output is correct
53	Correct	57 ms	55828 KB	Output is correct
54	Correct	58 ms	55768 KB	Output is correct
55	Correct	57 ms	55808 KB	Output is correct
56	Correct	59 ms	55888 KB	Output is correct
57	Correct	64 ms	55736 KB	Output is correct
58	Correct	63 ms	55856 KB	Output is correct
59	Correct	63 ms	55904 KB	Output is correct
60	Correct	57 ms	55760 KB	Output is correct
61	Correct	58 ms	55756 KB	Output is correct
62	Correct	74 ms	55964 KB	Output is correct
63	Correct	64 ms	55888 KB	Output is correct
64	Correct	64 ms	55868 KB	Output is correct
65	Correct	58 ms	55848 KB	Output is correct
66	Correct	57 ms	55888 KB	Output is correct
67	Correct	67 ms	54352 KB	Output is correct
68	Correct	68 ms	55744 KB	Output is correct
69	Correct	64 ms	55892 KB	Output is correct
70	Correct	64 ms	55756 KB	Output is correct
71	Correct	63 ms	55656 KB	Output is correct
72	Correct	63 ms	55988 KB	Output is correct
73	Correct	64 ms	55756 KB	Output is correct
74	Correct	58 ms	55736 KB	Output is correct
75	Correct	58 ms	55712 KB	Output is correct
76	Correct	57 ms	55736 KB	Output is correct
77	Correct	56 ms	55888 KB	Output is correct
78	Correct	558 ms	55480 KB	Output is correct
79	Correct	780 ms	55720 KB	Output is correct
80	Correct	758 ms	55772 KB	Output is correct
81	Correct	704 ms	55752 KB	Output is correct
82	Correct	710 ms	55880 KB	Output is correct
83	Correct	681 ms	55744 KB	Output is correct
84	Correct	672 ms	55756 KB	Output is correct
85	Correct	686 ms	55884 KB	Output is correct
86	Correct	652 ms	55764 KB	Output is correct
87	Correct	693 ms	55760 KB	Output is correct
88	Correct	710 ms	55772 KB	Output is correct
89	Correct	659 ms	55756 KB	Output is correct
90	Correct	637 ms	55856 KB	Output is correct
91	Correct	4 ms	9816 KB	Output is correct
92	Correct	5 ms	10840 KB	Output is correct
93	Correct	4 ms	10840 KB	Output is correct
94	Correct	65 ms	55744 KB	Output is correct
95	Correct	65 ms	56000 KB	Output is correct
96	Correct	63 ms	55812 KB	Output is correct
97	Correct	57 ms	55736 KB	Output is correct
98	Correct	59 ms	55748 KB	Output is correct
99	Correct	65 ms	55804 KB	Output is correct
100	Correct	64 ms	55692 KB	Output is correct
101	Correct	65 ms	55756 KB	Output is correct
102	Correct	59 ms	55744 KB	Output is correct
103	Correct	58 ms	55888 KB	Output is correct
104	Correct	7 ms	11252 KB	Output is correct
105	Correct	4 ms	10840 KB	Output is correct
106	Correct	5 ms	10840 KB	Output is correct
107	Correct	5 ms	10840 KB	Output is correct
108	Correct	5 ms	10840 KB	Output is correct
109	Correct	5 ms	10840 KB	Output is correct
110	Correct	5 ms	10840 KB	Output is correct
111	Correct	5 ms	10840 KB	Output is correct
112	Correct	5 ms	10840 KB	Output is correct
113	Correct	4 ms	10672 KB	Output is correct
114	Correct	190 ms	20576 KB	Output is correct
115	Correct	688 ms	55756 KB	Output is correct
116	Correct	691 ms	55852 KB	Output is correct
117	Correct	669 ms	55736 KB	Output is correct
118	Correct	723 ms	55756 KB	Output is correct
119	Correct	662 ms	55756 KB	Output is correct
120	Correct	661 ms	55752 KB	Output is correct
121	Correct	641 ms	55752 KB	Output is correct
122	Correct	597 ms	55736 KB	Output is correct
123	Correct	611 ms	55760 KB	Output is correct
124	Correct	572 ms	55888 KB	Output is correct
125	Correct	65 ms	55876 KB	Output is correct
126	Correct	65 ms	55888 KB	Output is correct
127	Correct	63 ms	55756 KB	Output is correct
128	Correct	56 ms	55756 KB	Output is correct
129	Correct	59 ms	55888 KB	Output is correct
130	Correct	65 ms	54328 KB	Output is correct
131	Correct	64 ms	55888 KB	Output is correct
132	Correct	63 ms	55892 KB	Output is correct
133	Correct	63 ms	55740 KB	Output is correct
134	Correct	62 ms	55888 KB	Output is correct
135	Correct	64 ms	55780 KB	Output is correct
136	Correct	67 ms	55836 KB	Output is correct
137	Correct	58 ms	55856 KB	Output is correct
138	Correct	56 ms	55652 KB	Output is correct
139	Correct	57 ms	55748 KB	Output is correct
140	Correct	57 ms	55888 KB	Output is correct
141	Correct	4 ms	10840 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	10840 KB	Output is correct
145	Correct	4 ms	10840 KB	Output is correct
146	Correct	4 ms	10328 KB	Output is correct
147	Correct	4 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	5 ms	10840 KB	Output is correct
151	Correct	5 ms	10840 KB	Output is correct
152	Correct	5 ms	10836 KB	Output is correct
153	Correct	5 ms	10840 KB	Output is correct
154	Correct	4 ms	11096 KB	Output is correct
155	Correct	5 ms	10840 KB	Output is correct
156	Correct	5 ms	10840 KB	Output is correct
157	Correct	693 ms	50508 KB	Output is correct
158	Correct	781 ms	55760 KB	Output is correct
159	Correct	746 ms	55740 KB	Output is correct
160	Correct	726 ms	55756 KB	Output is correct
161	Correct	692 ms	55868 KB	Output is correct
162	Correct	762 ms	55740 KB	Output is correct
163	Correct	719 ms	55736 KB	Output is correct
164	Correct	654 ms	55756 KB	Output is correct
165	Correct	729 ms	55744 KB	Output is correct
166	Correct	667 ms	55888 KB	Output is correct
167	Correct	732 ms	55680 KB	Output is correct
168	Correct	3 ms	9816 KB	Output is correct
169	Correct	470 ms	25460 KB	Output is correct
170	Correct	798 ms	55912 KB	Output is correct
171	Correct	796 ms	55888 KB	Output is correct
172	Correct	784 ms	55820 KB	Output is correct
173	Correct	812 ms	55888 KB	Output is correct
174	Correct	811 ms	55668 KB	Output is correct
175	Correct	784 ms	55888 KB	Output is correct
176	Correct	624 ms	55740 KB	Output is correct
177	Correct	694 ms	55752 KB	Output is correct
178	Correct	672 ms	55756 KB	Output is correct
179	Correct	663 ms	55820 KB	Output is correct

답안 #914867

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