Submission #941513

#	Time	Username	Problem	Language	Result	Execution time	Memory
941513		peterandvoi	Cat Exercise (JOI23_ho_t4)	C++17	41 / 100	25 ms	33088 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

#define int long long

const int N = (int) 2e5 + 5;
const int LOG = 18;

int n;
int p[N], lg[N];
int st[LOG][N];

int cmb(int a, int b) {
    return p[a] > p[b] ? a : b;
}

int get(int l, int r) {
    int k = lg[r - l + 1];
    return cmb(st[k][l], st[k][r - (1 << k) + 1]);
}

int dnc(int l, int r) {
    if (l == r) {
        return 0;
    }
    int mid = get(l, r);
    if (l == mid) {
        return abs(mid - get(l + 1, r)) + dnc(l + 1, r);
    }
    if (mid == r) {
        return abs(mid - get(l, r - 1)) + dnc(l, r - 1);
    }
    return max(abs(mid - get(mid + 1, r)) + dnc(mid + 1, r), abs(mid - get(l, mid - 1)) + dnc(l, mid - 1));
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        if (i > 1) {
            lg[i] = lg[i / 2] + 1;
        }
        cin >> p[i];
    }
    iota(st[0] + 1, st[0] + n + 1, 1);
    assert(lg[n] < LOG);
    for (int j = 1; j <= lg[n]; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            st[j][i] = cmb(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
        }
    }
    cout << dnc(1, n);
}

• 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