답안 #1040161

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1040161	2024-07-31T17:19:37 Z	TAhmed33	Cat Exercise (JOI23_ho_t4)	C++	41 / 100	27 ms	13916 KB

Main

    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 2e5 + 25;
    typedef long long ll;
    int a[MAXN], n;
    int nxt[MAXN], prv[MAXN];
    vector <int> adj[MAXN];
    ll dfs (int pos) {
        if (adj[pos].empty()) return 0;
        if ((int)adj[pos].size() == 1) {
            if (adj[pos][0] < pos) {
                return dfs(adj[pos][0]) + pos - adj[pos][0];
            } else {
                return dfs(adj[pos][0]) + adj[pos][0] - pos;
            }
        } else {
            return max(dfs(adj[pos][0]) + pos - adj[pos][0], dfs(adj[pos][1]) + adj[pos][1] - pos);
        }
    }
    void solve () {
        cin >> n;
        a[0] = 1e9;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        stack <int> cur;
        for (int i = 1; i <= n; i++) {
            while (!cur.empty() && a[i] > a[cur.top()]) {
                nxt[cur.top()] = i;
                cur.pop();
            }
            cur.push(i);
        }
        while (!cur.empty()) cur.pop();
        for (int i = n; i >= 1; i--) {
            while (!cur.empty() && a[i] > a[cur.top()]) {
                prv[cur.top()] = i;
                cur.pop();
            }
            cur.push(i);
        }
        while (!cur.empty()) cur.pop();
        for (int i = 1; i <= n; i++) {
            if (a[nxt[i]] < a[prv[i]]) {
                adj[nxt[i]].push_back(i);
            } else {
                adj[prv[i]].push_back(i);
            }
        }
        adj[0].clear();
        int root = -1;
        for (int i = 1; i <= n; i++) {
            if (a[i] == n) {
                root = i;
            }
        }
        cout << dfs(root) << '\n';
    }       
    signed main () {
        ios::sync_with_stdio(0); cin.tie(0);
        int tc = 1; //cin >> tc;
        while (tc--) solve();
    }

Subtask #1

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	6748 KB	Output is correct
2	Correct	2 ms	4956 KB	Output is correct
3	Correct	2 ms	4956 KB	Output is correct
4	Correct	1 ms	4956 KB	Output is correct
5	Correct	1 ms	6748 KB	Output is correct
6	Correct	1 ms	6748 KB	Output is correct
7	Correct	2 ms	4956 KB	Output is correct
8	Correct	1 ms	6748 KB	Output is correct
9	Correct	2 ms	6748 KB	Output is correct
10	Correct	3 ms	4956 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	6748 KB	Output is correct
2	Correct	2 ms	4956 KB	Output is correct
3	Correct	2 ms	4956 KB	Output is correct
4	Correct	1 ms	4956 KB	Output is correct
5	Correct	1 ms	6748 KB	Output is correct
6	Correct	1 ms	6748 KB	Output is correct
7	Correct	2 ms	4956 KB	Output is correct
8	Correct	1 ms	6748 KB	Output is correct
9	Correct	2 ms	6748 KB	Output is correct
10	Correct	3 ms	4956 KB	Output is correct
11	Correct	2 ms	4956 KB	Output is correct
12	Correct	1 ms	4956 KB	Output is correct
13	Correct	3 ms	4956 KB	Output is correct
14	Correct	2 ms	4956 KB	Output is correct
15	Correct	2 ms	4956 KB	Output is correct
16	Correct	2 ms	4956 KB	Output is correct
17	Correct	2 ms	4956 KB	Output is correct

Subtask #3

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	6748 KB	Output is correct
2	Correct	2 ms	4956 KB	Output is correct
3	Correct	2 ms	4956 KB	Output is correct
4	Correct	1 ms	4956 KB	Output is correct
5	Correct	1 ms	6748 KB	Output is correct
6	Correct	1 ms	6748 KB	Output is correct
7	Correct	2 ms	4956 KB	Output is correct
8	Correct	1 ms	6748 KB	Output is correct
9	Correct	2 ms	6748 KB	Output is correct
10	Correct	3 ms	4956 KB	Output is correct
11	Correct	2 ms	4956 KB	Output is correct
12	Correct	1 ms	4956 KB	Output is correct
13	Correct	3 ms	4956 KB	Output is correct
14	Correct	2 ms	4956 KB	Output is correct
15	Correct	2 ms	4956 KB	Output is correct
16	Correct	2 ms	4956 KB	Output is correct
17	Correct	2 ms	4956 KB	Output is correct
18	Correct	3 ms	5212 KB	Output is correct
19	Correct	2 ms	5212 KB	Output is correct
20	Correct	2 ms	6748 KB	Output is correct
21	Correct	2 ms	6756 KB	Output is correct
22	Correct	3 ms	5328 KB	Output is correct
23	Correct	2 ms	5212 KB	Output is correct
24	Correct	3 ms	5212 KB	Output is correct

Subtask #4

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	6748 KB	Output is correct
2	Correct	2 ms	4956 KB	Output is correct
3	Correct	2 ms	4956 KB	Output is correct
4	Correct	1 ms	4956 KB	Output is correct
5	Correct	1 ms	6748 KB	Output is correct
6	Correct	1 ms	6748 KB	Output is correct
7	Correct	2 ms	4956 KB	Output is correct
8	Correct	1 ms	6748 KB	Output is correct
9	Correct	2 ms	6748 KB	Output is correct
10	Correct	3 ms	4956 KB	Output is correct
11	Correct	2 ms	4956 KB	Output is correct
12	Correct	1 ms	4956 KB	Output is correct
13	Correct	3 ms	4956 KB	Output is correct
14	Correct	2 ms	4956 KB	Output is correct
15	Correct	2 ms	4956 KB	Output is correct
16	Correct	2 ms	4956 KB	Output is correct
17	Correct	2 ms	4956 KB	Output is correct
18	Correct	3 ms	5212 KB	Output is correct
19	Correct	2 ms	5212 KB	Output is correct
20	Correct	2 ms	6748 KB	Output is correct
21	Correct	2 ms	6756 KB	Output is correct
22	Correct	3 ms	5328 KB	Output is correct
23	Correct	2 ms	5212 KB	Output is correct
24	Correct	3 ms	5212 KB	Output is correct
25	Correct	2 ms	4952 KB	Output is correct
26	Incorrect	2 ms	5212 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	6748 KB	Output is correct
2	Correct	2 ms	4956 KB	Output is correct
3	Correct	2 ms	4956 KB	Output is correct
4	Correct	1 ms	4956 KB	Output is correct
5	Correct	1 ms	6748 KB	Output is correct
6	Correct	1 ms	6748 KB	Output is correct
7	Correct	2 ms	4956 KB	Output is correct
8	Correct	1 ms	6748 KB	Output is correct
9	Correct	2 ms	6748 KB	Output is correct
10	Correct	3 ms	4956 KB	Output is correct
11	Correct	2 ms	4956 KB	Output is correct
12	Correct	1 ms	4956 KB	Output is correct
13	Correct	3 ms	4956 KB	Output is correct
14	Correct	2 ms	4956 KB	Output is correct
15	Correct	2 ms	4956 KB	Output is correct
16	Correct	2 ms	4956 KB	Output is correct
17	Correct	2 ms	4956 KB	Output is correct
18	Correct	3 ms	5212 KB	Output is correct
19	Correct	2 ms	5212 KB	Output is correct
20	Correct	2 ms	6748 KB	Output is correct
21	Correct	2 ms	6756 KB	Output is correct
22	Correct	3 ms	5328 KB	Output is correct
23	Correct	2 ms	5212 KB	Output is correct
24	Correct	3 ms	5212 KB	Output is correct
25	Correct	19 ms	13548 KB	Output is correct
26	Correct	24 ms	13848 KB	Output is correct
27	Correct	23 ms	13916 KB	Output is correct
28	Correct	26 ms	11612 KB	Output is correct
29	Correct	24 ms	11568 KB	Output is correct
30	Correct	24 ms	11604 KB	Output is correct
31	Correct	27 ms	11612 KB	Output is correct

Subtask #6

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4956 KB	Output is correct
2	Incorrect	2 ms	5116 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #7

0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	6748 KB	Output is correct
2	Correct	2 ms	4956 KB	Output is correct
3	Correct	2 ms	4956 KB	Output is correct
4	Correct	1 ms	4956 KB	Output is correct
5	Correct	1 ms	6748 KB	Output is correct
6	Correct	1 ms	6748 KB	Output is correct
7	Correct	2 ms	4956 KB	Output is correct
8	Correct	1 ms	6748 KB	Output is correct
9	Correct	2 ms	6748 KB	Output is correct
10	Correct	3 ms	4956 KB	Output is correct
11	Correct	2 ms	4956 KB	Output is correct
12	Correct	1 ms	4956 KB	Output is correct
13	Correct	3 ms	4956 KB	Output is correct
14	Correct	2 ms	4956 KB	Output is correct
15	Correct	2 ms	4956 KB	Output is correct
16	Correct	2 ms	4956 KB	Output is correct
17	Correct	2 ms	4956 KB	Output is correct
18	Correct	3 ms	5212 KB	Output is correct
19	Correct	2 ms	5212 KB	Output is correct
20	Correct	2 ms	6748 KB	Output is correct
21	Correct	2 ms	6756 KB	Output is correct
22	Correct	3 ms	5328 KB	Output is correct
23	Correct	2 ms	5212 KB	Output is correct
24	Correct	3 ms	5212 KB	Output is correct
25	Correct	2 ms	4952 KB	Output is correct
26	Incorrect	2 ms	5212 KB	Output isn't correct
27	Halted	0 ms	0 KB	-