답안 #850711

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
850711 2023-09-17T10:11:57 Z danikoynov Tourism (JOI23_tourism) C++14
100 / 100
410 ms 49744 KB
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10;

struct query
{
    int l, r, idx;
} task[maxn];

int n, m, c[maxn], q;
vector < int > adj[maxn];

void input()
{
    cin >> n >> m >> q;
    for (int i = 1; i < n; i ++)
    {
        int v, u;
        cin >> v >> u;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }

    for (int i = 1; i <= m; i ++)
    {
        cin >> c[i];
    }

    for (int i = 1; i <= q; i ++)
    {
        cin >> task[i].l >> task[i].r;
        task[i].idx = i;
    }
}


int depth[maxn], tin[maxn], tout[maxn];
int occ[2 * maxn], rev[2 * maxn], timer;
int sub[maxn], heavy[maxn];

void euler(int v = 1, int p = - 1)
{
    occ[++ timer] = v;
    tin[v] = timer;
    rev[timer] = v;
    sub[v] = 1;
    heavy[v] = -1;
    for (int u : adj[v])
    {
        if (u == p)
            continue;
        depth[u] = depth[v] + 1;
        euler(u, v);
        if (heavy[v] == -1 || sub[u] > sub[heavy[v]])
            heavy[v] = u;
        sub[v] += sub[u];
        occ[++ timer] = v;
    }
    tout[v] = timer;
}

const int maxlog = 20;

int lg[2 * maxn], dp[maxlog][2 * maxn];

void sparse_table()
{
    for (int i = 1; i <= timer; i ++)
    {
        lg[i] = lg[i / 2] + 1;
        dp[0][i] = occ[i];
    }

    for (int j = 1; j < lg[timer]; j ++)
        for (int i = 1; i <= timer - (1 << j); i ++)
        {
            dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
            if (depth[dp[j - 1][i]] < depth[dp[j][i]])
                dp[j][i] = dp[j - 1][i];
        }
}

int get_lca(int v, int u)
{
    int l = tin[v], r = tin[u];
    if (l > r)
        swap(l, r);
    int len = lg[r - l + 1] - 1;
    int lca = dp[len][r - (1 << len) + 1];
    if (depth[dp[len][l]] < depth[lca])
        lca = dp[len][l];
    return lca;
}

int get_distance(int v, int u)
{
    return depth[v] + depth[u] - 2 * depth[get_lca(v, u)];
}

struct interval
{
    int left, right, value;

    interval(int _left = 0, int _right = 0, int _value = 0)
    {
        left = _left;
        right = _right;
        value = _value;
    }
    bool operator < (const interval seg) const
    {
        if (left == seg.left)
        {
            if (value == seg.value)
                assert(right == seg.right);
            /// values cannot be the same
            return value > seg.value;

        }
        else
            return left < seg.left;
    }
};
struct chain
{
    int top, left, right;


    set < interval > act;
} st[maxn];

int ch_idx[maxn], ch_cnt, ord[maxn], last, ch_pos[maxn];

void hld(int v = 1, int p = -1)
{
    ///cout << v << " : " << p << endl;
    ch_idx[v] = ch_cnt;
    ord[++ last] = v;
    ch_pos[v] = last;
    st[ch_idx[v]].right = last;
    if (heavy[v] != -1)
        hld(heavy[v], v);
    for (int u : adj[v])
    {
        if (u == p || u == heavy[v])
            continue;
        ch_cnt ++;
        st[ch_cnt].top = v;
        st[ch_cnt].left = last + 1;
        st[ch_cnt].right = last + 1;
        hld(u, v);
    }
}

void decompose()
{
    ch_idx[1] = 1;
    ch_cnt = 1;
    ch_pos[1] = 1;
    st[ch_cnt].left = st[ch_cnt].right = 1;
    st[ch_cnt].top = 0;
    hld();

    /**cout << ch_cnt << endl;
    for (int i = 1; i <= ch_cnt; i ++)
        cout << st[i].left << " " << st[i].right << endl;
    for (int i = 1; i <= n; i ++)
    cout << ord[i] << " ";
    cout << endl;*/
}

int fen[maxn];

void update(int v, int val)
{
    for (int i = v; i <= m; i += (i & -i))
        fen[i] += val;
}

int query_sum(int v)
{
    int s = 0;
    for (int i = v; i > 0; i -= (i & -i))
        s += fen[i];
    return s;
}

int col[maxn];
void write_on_chain(int idx, int left, int right, int val)
{
    /**for (int i = left; i <= right; i ++)
    {
        if (col[i] != 0)
            update(col[i], - 1);
        col[i] = val;
    }*/
    ///update(val, right - left + 1);
    ///return;
    interval seg(left, right, val);


    st[idx].act.insert(seg);
    set < interval > :: iterator it, bef, aft;
    it = st[idx].act.find(seg);
    update(val, right - left + 1);
    ///cout << "write on chain " << val << " " << left << " " << right << endl;
    if (it != st[idx].act.begin())
    {
        bef = prev(it);

        if (bef -> right >= right)
        {
            update(bef -> value, - (right - left + 1));
            interval lf_split(bef -> left, left - 1, bef -> value);
            interval rf_split(right + 1, bef -> right, bef -> value);
            st[idx].act.erase(bef);
            if (lf_split.left <= lf_split.right)
                st[idx].act.insert(lf_split);
            if (rf_split.left <= rf_split.right)
                st[idx].act.insert(rf_split);
        }
        else if (bef -> right >= left)
        {

            update(bef -> value, - (bef -> right - left + 1));

            interval new_bef(bef -> left, left - 1, bef -> value);
            st[idx].act.erase(bef);
            if (new_bef.left <= new_bef.right)
                st[idx].act.insert(new_bef);
        }
    }

    while(true)
    {

        it = st[idx].act.find(seg);
        if (next(it) != st[idx].act.end())
        {
            aft = next(it);
            if (aft -> right <= right)
            {
                update(aft -> value, - (aft -> right - aft -> left + 1));
                st[idx].act.erase(aft);
                continue;
            }
            if (aft -> left <= right)
            {
                update(aft -> value, - (right - aft -> left + 1));
                interval new_aft(right + 1, aft -> right, aft -> value);
                st[idx].act.erase(aft);
                if (new_aft.left <= new_aft.right)
                    st[idx].act.insert(new_aft);
            }
            break;
        }
        else
            break;


    }

    /**if (idx != 25)
        return;
    cout << "writing " << idx << endl;
    cout << "add " << left << " " << right << endl;
        for (interval cur : st[idx].act)
    {

        cout << cur.left << " " << cur.right << " " << cur.value << endl;
    }
    for (interval cur : st[idx].act)
    {
        for (int j  = cur.left; j <= cur.right; j ++)
        {
            if (col[j] != cur.value)
            {
                cout <<" wtf " << endl;
                //exit(0);
            }
        }

    }*/
}

void write_on_path(int v, int p, int val)
{
    ///cout << "write on path " << v << " " << p << endl;
    while(ch_idx[v] != ch_idx[p])
    {
        write_on_chain(ch_idx[v], st[ch_idx[v]].left, ch_pos[v], val);
        v = st[ch_idx[v]].top;
    }


    if (ch_pos[p] < ch_pos[v])
        write_on_chain(ch_idx[v], ch_pos[p] + 1, ch_pos[v], val);

}


vector < query > ask[maxn];
int res[maxn];
void queries()
{

    ///q = 1;
    for (int i = 1; i <= q; i ++)
        ask[task[i].l].push_back(task[i]);

    for (int i = m; i > 0; i --)
    {
        if (i != m)
        {
            int v = c[i], u = c[i + 1];
            int lca = get_lca(v, u);
            write_on_path(v, lca, i);
            write_on_path(u, lca, i);
        }
        /**cout << "step " << i << endl;
        for (int j = 1; j <= m; j ++)
            cout << query_sum(j) - query_sum(j - 1) << " ";
        cout << endl;*/
        for (query cur : ask[i])
        {
            res[cur.idx] = query_sum(cur.r - 1) + 1;
        }
    }


    for (int i = 1; i <= q; i ++)
        cout << res[i] << endl;
}

void solve()
{
    input();
    euler();
    sparse_table();
    decompose();
    queries();

}

int main()
{
    ///freopen("test.txt", "r", stdin);
    speed();
    solve();
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 3 ms 19032 KB Output is correct
3 Correct 3 ms 19036 KB Output is correct
4 Correct 5 ms 23132 KB Output is correct
5 Correct 4 ms 23128 KB Output is correct
6 Correct 5 ms 23128 KB Output is correct
7 Correct 5 ms 23128 KB Output is correct
8 Correct 4 ms 23128 KB Output is correct
9 Correct 4 ms 23128 KB Output is correct
10 Correct 4 ms 23128 KB Output is correct
11 Correct 4 ms 23132 KB Output is correct
12 Correct 4 ms 23128 KB Output is correct
13 Correct 4 ms 23128 KB Output is correct
14 Correct 4 ms 23128 KB Output is correct
15 Correct 4 ms 23132 KB Output is correct
16 Correct 4 ms 23128 KB Output is correct
17 Correct 4 ms 23128 KB Output is correct
18 Correct 4 ms 23128 KB Output is correct
19 Correct 4 ms 23128 KB Output is correct
20 Correct 4 ms 23128 KB Output is correct
21 Correct 4 ms 23128 KB Output is correct
22 Correct 4 ms 23128 KB Output is correct
23 Correct 4 ms 23128 KB Output is correct
24 Correct 5 ms 23128 KB Output is correct
25 Correct 4 ms 23128 KB Output is correct
26 Correct 3 ms 23288 KB Output is correct
27 Correct 3 ms 16988 KB Output is correct
28 Correct 4 ms 23128 KB Output is correct
29 Correct 4 ms 23128 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 3 ms 19032 KB Output is correct
3 Correct 3 ms 19036 KB Output is correct
4 Correct 5 ms 23132 KB Output is correct
5 Correct 4 ms 23128 KB Output is correct
6 Correct 5 ms 23128 KB Output is correct
7 Correct 5 ms 23128 KB Output is correct
8 Correct 4 ms 23128 KB Output is correct
9 Correct 4 ms 23128 KB Output is correct
10 Correct 4 ms 23128 KB Output is correct
11 Correct 4 ms 23132 KB Output is correct
12 Correct 4 ms 23128 KB Output is correct
13 Correct 4 ms 23128 KB Output is correct
14 Correct 4 ms 23128 KB Output is correct
15 Correct 4 ms 23132 KB Output is correct
16 Correct 4 ms 23128 KB Output is correct
17 Correct 4 ms 23128 KB Output is correct
18 Correct 4 ms 23128 KB Output is correct
19 Correct 4 ms 23128 KB Output is correct
20 Correct 4 ms 23128 KB Output is correct
21 Correct 4 ms 23128 KB Output is correct
22 Correct 4 ms 23128 KB Output is correct
23 Correct 4 ms 23128 KB Output is correct
24 Correct 5 ms 23128 KB Output is correct
25 Correct 4 ms 23128 KB Output is correct
26 Correct 3 ms 23288 KB Output is correct
27 Correct 3 ms 16988 KB Output is correct
28 Correct 4 ms 23128 KB Output is correct
29 Correct 4 ms 23128 KB Output is correct
30 Correct 6 ms 25436 KB Output is correct
31 Correct 6 ms 25432 KB Output is correct
32 Correct 7 ms 25436 KB Output is correct
33 Correct 7 ms 25436 KB Output is correct
34 Correct 6 ms 25432 KB Output is correct
35 Correct 7 ms 25432 KB Output is correct
36 Correct 7 ms 25432 KB Output is correct
37 Correct 6 ms 25436 KB Output is correct
38 Correct 6 ms 25436 KB Output is correct
39 Correct 6 ms 25688 KB Output is correct
40 Correct 6 ms 25688 KB Output is correct
41 Correct 6 ms 25848 KB Output is correct
42 Correct 5 ms 25692 KB Output is correct
43 Correct 5 ms 25432 KB Output is correct
44 Correct 6 ms 25432 KB Output is correct
45 Correct 6 ms 25432 KB Output is correct
46 Correct 6 ms 25436 KB Output is correct
47 Correct 6 ms 25432 KB Output is correct
48 Correct 6 ms 25432 KB Output is correct
49 Correct 6 ms 25436 KB Output is correct
50 Correct 5 ms 25432 KB Output is correct
51 Correct 5 ms 25432 KB Output is correct
52 Correct 6 ms 25432 KB Output is correct
53 Correct 5 ms 25436 KB Output is correct
54 Correct 5 ms 25432 KB Output is correct
55 Correct 5 ms 25432 KB Output is correct
56 Correct 3 ms 17244 KB Output is correct
57 Correct 5 ms 25432 KB Output is correct
58 Correct 8 ms 25436 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 17244 KB Output is correct
4 Correct 85 ms 39952 KB Output is correct
5 Correct 75 ms 42700 KB Output is correct
6 Correct 86 ms 44000 KB Output is correct
7 Correct 102 ms 46776 KB Output is correct
8 Correct 102 ms 49744 KB Output is correct
9 Correct 118 ms 49704 KB Output is correct
10 Correct 107 ms 49644 KB Output is correct
11 Correct 103 ms 49648 KB Output is correct
12 Correct 111 ms 49488 KB Output is correct
13 Correct 100 ms 49488 KB Output is correct
14 Correct 99 ms 49408 KB Output is correct
15 Correct 50 ms 46668 KB Output is correct
16 Correct 112 ms 49496 KB Output is correct
17 Correct 33 ms 22556 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 101 ms 34572 KB Output is correct
3 Correct 160 ms 35328 KB Output is correct
4 Correct 123 ms 35676 KB Output is correct
5 Correct 184 ms 38480 KB Output is correct
6 Correct 205 ms 38580 KB Output is correct
7 Correct 198 ms 38480 KB Output is correct
8 Correct 211 ms 38480 KB Output is correct
9 Correct 201 ms 38576 KB Output is correct
10 Correct 198 ms 38492 KB Output is correct
11 Correct 198 ms 38672 KB Output is correct
12 Correct 200 ms 38840 KB Output is correct
13 Correct 219 ms 39152 KB Output is correct
14 Correct 222 ms 40228 KB Output is correct
15 Correct 216 ms 43344 KB Output is correct
16 Correct 219 ms 39096 KB Output is correct
17 Correct 224 ms 38992 KB Output is correct
18 Correct 208 ms 39000 KB Output is correct
19 Correct 159 ms 35760 KB Output is correct
20 Correct 158 ms 35652 KB Output is correct
21 Correct 153 ms 35412 KB Output is correct
22 Correct 156 ms 35664 KB Output is correct
23 Correct 146 ms 35408 KB Output is correct
24 Correct 152 ms 35408 KB Output is correct
25 Correct 153 ms 35668 KB Output is correct
26 Correct 152 ms 35496 KB Output is correct
27 Correct 171 ms 35676 KB Output is correct
28 Correct 151 ms 35636 KB Output is correct
29 Correct 158 ms 35744 KB Output is correct
30 Correct 164 ms 36388 KB Output is correct
31 Correct 159 ms 35924 KB Output is correct
32 Correct 176 ms 36796 KB Output is correct
33 Correct 170 ms 38068 KB Output is correct
34 Correct 186 ms 40332 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 17240 KB Output is correct
4 Correct 258 ms 39208 KB Output is correct
5 Correct 280 ms 39236 KB Output is correct
6 Correct 306 ms 41656 KB Output is correct
7 Correct 332 ms 43176 KB Output is correct
8 Correct 351 ms 43088 KB Output is correct
9 Correct 345 ms 43156 KB Output is correct
10 Correct 384 ms 43140 KB Output is correct
11 Correct 358 ms 42992 KB Output is correct
12 Correct 410 ms 42952 KB Output is correct
13 Correct 341 ms 43084 KB Output is correct
14 Correct 34 ms 21072 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 3 ms 19032 KB Output is correct
3 Correct 3 ms 19036 KB Output is correct
4 Correct 5 ms 23132 KB Output is correct
5 Correct 4 ms 23128 KB Output is correct
6 Correct 5 ms 23128 KB Output is correct
7 Correct 5 ms 23128 KB Output is correct
8 Correct 4 ms 23128 KB Output is correct
9 Correct 4 ms 23128 KB Output is correct
10 Correct 4 ms 23128 KB Output is correct
11 Correct 4 ms 23132 KB Output is correct
12 Correct 4 ms 23128 KB Output is correct
13 Correct 4 ms 23128 KB Output is correct
14 Correct 4 ms 23128 KB Output is correct
15 Correct 4 ms 23132 KB Output is correct
16 Correct 4 ms 23128 KB Output is correct
17 Correct 4 ms 23128 KB Output is correct
18 Correct 4 ms 23128 KB Output is correct
19 Correct 4 ms 23128 KB Output is correct
20 Correct 4 ms 23128 KB Output is correct
21 Correct 4 ms 23128 KB Output is correct
22 Correct 4 ms 23128 KB Output is correct
23 Correct 4 ms 23128 KB Output is correct
24 Correct 5 ms 23128 KB Output is correct
25 Correct 4 ms 23128 KB Output is correct
26 Correct 3 ms 23288 KB Output is correct
27 Correct 3 ms 16988 KB Output is correct
28 Correct 4 ms 23128 KB Output is correct
29 Correct 4 ms 23128 KB Output is correct
30 Correct 6 ms 25436 KB Output is correct
31 Correct 6 ms 25432 KB Output is correct
32 Correct 7 ms 25436 KB Output is correct
33 Correct 7 ms 25436 KB Output is correct
34 Correct 6 ms 25432 KB Output is correct
35 Correct 7 ms 25432 KB Output is correct
36 Correct 7 ms 25432 KB Output is correct
37 Correct 6 ms 25436 KB Output is correct
38 Correct 6 ms 25436 KB Output is correct
39 Correct 6 ms 25688 KB Output is correct
40 Correct 6 ms 25688 KB Output is correct
41 Correct 6 ms 25848 KB Output is correct
42 Correct 5 ms 25692 KB Output is correct
43 Correct 5 ms 25432 KB Output is correct
44 Correct 6 ms 25432 KB Output is correct
45 Correct 6 ms 25432 KB Output is correct
46 Correct 6 ms 25436 KB Output is correct
47 Correct 6 ms 25432 KB Output is correct
48 Correct 6 ms 25432 KB Output is correct
49 Correct 6 ms 25436 KB Output is correct
50 Correct 5 ms 25432 KB Output is correct
51 Correct 5 ms 25432 KB Output is correct
52 Correct 6 ms 25432 KB Output is correct
53 Correct 5 ms 25436 KB Output is correct
54 Correct 5 ms 25432 KB Output is correct
55 Correct 5 ms 25432 KB Output is correct
56 Correct 3 ms 17244 KB Output is correct
57 Correct 5 ms 25432 KB Output is correct
58 Correct 8 ms 25436 KB Output is correct
59 Correct 3 ms 19032 KB Output is correct
60 Correct 3 ms 16988 KB Output is correct
61 Correct 3 ms 17244 KB Output is correct
62 Correct 85 ms 39952 KB Output is correct
63 Correct 75 ms 42700 KB Output is correct
64 Correct 86 ms 44000 KB Output is correct
65 Correct 102 ms 46776 KB Output is correct
66 Correct 102 ms 49744 KB Output is correct
67 Correct 118 ms 49704 KB Output is correct
68 Correct 107 ms 49644 KB Output is correct
69 Correct 103 ms 49648 KB Output is correct
70 Correct 111 ms 49488 KB Output is correct
71 Correct 100 ms 49488 KB Output is correct
72 Correct 99 ms 49408 KB Output is correct
73 Correct 50 ms 46668 KB Output is correct
74 Correct 112 ms 49496 KB Output is correct
75 Correct 33 ms 22556 KB Output is correct
76 Correct 3 ms 19032 KB Output is correct
77 Correct 101 ms 34572 KB Output is correct
78 Correct 160 ms 35328 KB Output is correct
79 Correct 123 ms 35676 KB Output is correct
80 Correct 184 ms 38480 KB Output is correct
81 Correct 205 ms 38580 KB Output is correct
82 Correct 198 ms 38480 KB Output is correct
83 Correct 211 ms 38480 KB Output is correct
84 Correct 201 ms 38576 KB Output is correct
85 Correct 198 ms 38492 KB Output is correct
86 Correct 198 ms 38672 KB Output is correct
87 Correct 200 ms 38840 KB Output is correct
88 Correct 219 ms 39152 KB Output is correct
89 Correct 222 ms 40228 KB Output is correct
90 Correct 216 ms 43344 KB Output is correct
91 Correct 219 ms 39096 KB Output is correct
92 Correct 224 ms 38992 KB Output is correct
93 Correct 208 ms 39000 KB Output is correct
94 Correct 159 ms 35760 KB Output is correct
95 Correct 158 ms 35652 KB Output is correct
96 Correct 153 ms 35412 KB Output is correct
97 Correct 156 ms 35664 KB Output is correct
98 Correct 146 ms 35408 KB Output is correct
99 Correct 152 ms 35408 KB Output is correct
100 Correct 153 ms 35668 KB Output is correct
101 Correct 152 ms 35496 KB Output is correct
102 Correct 171 ms 35676 KB Output is correct
103 Correct 151 ms 35636 KB Output is correct
104 Correct 158 ms 35744 KB Output is correct
105 Correct 164 ms 36388 KB Output is correct
106 Correct 159 ms 35924 KB Output is correct
107 Correct 176 ms 36796 KB Output is correct
108 Correct 170 ms 38068 KB Output is correct
109 Correct 186 ms 40332 KB Output is correct
110 Correct 3 ms 19032 KB Output is correct
111 Correct 3 ms 16988 KB Output is correct
112 Correct 3 ms 17240 KB Output is correct
113 Correct 258 ms 39208 KB Output is correct
114 Correct 280 ms 39236 KB Output is correct
115 Correct 306 ms 41656 KB Output is correct
116 Correct 332 ms 43176 KB Output is correct
117 Correct 351 ms 43088 KB Output is correct
118 Correct 345 ms 43156 KB Output is correct
119 Correct 384 ms 43140 KB Output is correct
120 Correct 358 ms 42992 KB Output is correct
121 Correct 410 ms 42952 KB Output is correct
122 Correct 341 ms 43084 KB Output is correct
123 Correct 34 ms 21072 KB Output is correct
124 Correct 203 ms 45136 KB Output is correct
125 Correct 157 ms 42064 KB Output is correct
126 Correct 249 ms 45576 KB Output is correct
127 Correct 228 ms 45648 KB Output is correct
128 Correct 234 ms 45648 KB Output is correct
129 Correct 267 ms 45632 KB Output is correct
130 Correct 226 ms 45648 KB Output is correct
131 Correct 115 ms 48464 KB Output is correct
132 Correct 112 ms 49488 KB Output is correct
133 Correct 112 ms 45756 KB Output is correct
134 Correct 189 ms 42644 KB Output is correct
135 Correct 194 ms 42536 KB Output is correct
136 Correct 214 ms 43260 KB Output is correct
137 Correct 102 ms 46536 KB Output is correct
138 Correct 100 ms 46356 KB Output is correct
139 Correct 98 ms 46384 KB Output is correct
140 Correct 117 ms 46340 KB Output is correct
141 Correct 107 ms 46536 KB Output is correct
142 Correct 98 ms 46536 KB Output is correct
143 Correct 65 ms 39328 KB Output is correct
144 Correct 266 ms 45240 KB Output is correct