oj.uz

Submission #538922

# Submission time Handle Problem Language Result Execution time Memory
538922 2022-03-18T04:26:29 Z Monarchuwu Triple Jump (JOI19_jumps) C++17
0 / 100
 168 ms 5868 KB 
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

typedef pair<int, int> pii;
#define ff first
#define ss second

const int N = 5e5 + 5, inf = 1e9 + 7;
int n;
int a[N];

pii seg[1 << 20];
int ma[1 << 20];
pii Merge(pii u, pii v) {
    pii c;
    if (a[u.ff] > a[v.ff])
        c.ff = u.ff, u.ff = u.ss;
    else c.ff = v.ff, v.ff = v.ss;
    c.ss = a[u.ff] > a[v.ff] ? u.ff : v.ff;
    return c;
}
void build() {
    for (int i = 1; i <= n; ++i) {
        seg[i + n - 1].ff = i;
        ma[i + n - 1] = a[i];
    }
    for (int i = n - 1; i; --i) {
        seg[i] = Merge(seg[i << 1], seg[i << 1 | 1]);
        ma[i] = max(ma[i << 1], ma[i << 1 | 1]);
    }
}
void upd(int p) {
    seg[p + n - 1].ff = 0;
    for (p += n - 1, p >>= 1; p; p >>= 1)
        seg[p] = Merge(seg[p << 1], seg[p << 1 | 1]);
}
pii get_pos(int l, int r) {
    pii ans(0, 0);
    for (l += n - 1, r += n; l < r; l >>= 1, r >>= 1) {
        if (l & 1) ans = Merge(ans, seg[l++]);
        if (r & 1) ans = Merge(ans, seg[--r]);
    }
    return ans;
}
int get_max(int l, int r) {
    int ans(-inf);
    for (l += n - 1, r += n; l < r; l >>= 1, r >>= 1) {
        if (l & 1) ans = max(ans, ma[l++]);
        if (r & 1) ans = max(ans, ma[--r]);
    }
    return ans;
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    build();

    int ans(-inf);
    for (int cnt = n; cnt > 2; --cnt) {
        pii p = get_pos(1, n);
        int p1 = p.ff, p2 = p.ss;
        if (p1 > p2) swap(p1, p2);
        
        ans = max(ans, a[p1] + a[p2] + max({ get_max(1, p1 * 2 - p2), get_max(p1 + 1,(p1 + p2) >> 1), get_max(p2 * 2 - p1, n) }));
        upd(p.ff);
    }
    cout << ans << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 5796 KB Output is correct
2 Correct 76 ms 5868 KB Output is correct
3 Correct 75 ms 5800 KB Output is correct
4 Incorrect 168 ms 5800 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -