Submission #1040161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040161		TAhmed33	Cat Exercise (JOI23_ho_t4)	C++98	41 / 100	27 ms	13916 KiB

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 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26