Submission #1084779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084779		underwaterkillerwhale	Triple Jump (JOI19_jumps)	C++17	100 / 100	782 ms	331916 KiB

jumps

#include <bits/stdc++.h>
#define ll              long long
#define pii             pair<int,int>
#define pll             pair<ll,ll>
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
#define iter(id, v)     for(auto id : v)
#define fs              first
#define se              second
#define MP              make_pair
#define pb              push_back
#define bit(msk, i)     ((msk >> i) & 1)
#define SZ(v)           (ll)v.size()
#define ALL(v)          v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 5e5 + 2;
const int Mod = 1e9 + 7;
const ll INF = 1e16;
const ll BASE = 137;
const int szBL = 350;

int n, Q;
int a[N];
pii qr[N];
int prv[N];

struct Segment_Tree {
    int m;
    ll Val[N << 2], st[N << 2], lz[N << 2];

    void init (int n)  {
        m = n;
        rep (i, 1, n << 2) lz[i] = -INF;
    }

    void build (int id, int l, int r) {
        if (l == r) {
            st[id] = a[l];
            return;
        }
        int mid = l + r >> 1;
        down(id);
        build (id << 1, l, mid);
        build (id << 1 | 1, mid + 1, r);
        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }

    void down (int id) {
        if (lz[id] != -1) {
            rep (i, id << 1, id << 1 | 1) {
                lz[i] = max(lz[id], lz[i]);
                Val[i] = max(Val[i], lz[i] + st[i]);
            }
            lz[id] = -INF;
        }
    }

    void update (int id, int l, int r, int u, int v, ll val) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            lz[id] = max(lz[id], val);
            Val[id] = max(Val[id], st[id] + lz[id]);
            return;
        }
        int mid = l + r >> 1;
        down(id);
        update (id << 1, l, mid, u, v, val);
        update (id << 1 | 1, mid + 1, r, u, v, val);
        Val[id] = max(Val[id << 1], Val[id << 1 | 1]);
    }

    ll get (int id, int l, int r, int u, int v) {
        if (l > v || r < u) return -INF;
        if (l >= u && r <= v) return Val[id];
        int mid = l + r >> 1;
        down(id);
        return max(get (id << 1, l, mid, u, v),
                    get (id << 1 | 1, mid + 1, r, u, v));
    }

    void update (int u, int v, ll val) {
        update (1, 1, m, u, v, val);
    }
    ll get (int u, int v) {
        return get (1, 1, m, u, v);
    }
}ST;

namespace sub3 {
    void solution() {
        ST.init(n);
        ST.build(1, 1, n);
        stack<pii> st;
        vector<pii> candi;
        rep (i, 1, n) {
            while (!st.empty() && st.top().fs < a[i]) st.pop();
            if (!st.empty()) {
                prv[i] = st.top().se;
            }
            st.push({a[i], i});
            int u = i - 1;
            while (u != 0 && a[u] < a[i]) {
                candi.pb(MP(u, i));
                u = prv[u];
            }
            if (u != 0) candi.pb(MP(u, i));
        }
        iter (&id, candi)
            ST.update (2 * id.se - id.fs, n, a[id.se] + a[id.fs]);
        cout << ST.Val[1] <<"\n";
    }
}

namespace sub2 {
    const int N2 = 5e3 + 7;
    ll dp[N2][N2];
    int mx[N2][N2];

    void solution() {
        memset (dp, -0x3f, sizeof dp);
        memset (mx, -0x3f, sizeof mx);
        rep (i, 1, n) {
            rep (j, i, n) {
                mx[i][j] = max(mx[i][j - 1], a[j]);
            }
        }
        reb (i, n, 1) {
            rep (j, i + 1, n) {
                dp[i][j] = max({dp[i + 1][j], dp[i][j - 1]});
                int mid = j + i >> 1;
                dp[i][j] = max(dp[i][j], 1LL*a[i] + a[j] + mx[i + 1][mid]);
            }
        }
        rep (i, 1, Q) {
            cout << dp[qr[i].fs][qr[i].se] <<"\n";
        }
    }
}

namespace sub4 {
    vector<int> candi[N];
    vector<pii> queries[N];
    ll Ans[N];

    void solution () {
        ST.init(n);
        ST.build(1, 1, n);
        stack<pii> st;
        rep (i, 1, n) {
            while (!st.empty() && st.top().fs < a[i]) st.pop();
            if (!st.empty()) {
                prv[i] = st.top().se;
            }
            st.push({a[i], i});
            int u = i - 1;
            while (u != 0 && a[u] < a[i]) {
                candi[u].pb(i);
                u = prv[u];
            }
            if (u != 0) candi[u].pb(i);
        }
        rep (i, 1, Q) queries[qr[i].fs].pb(MP(qr[i].se, i));
        reb (i, n, 1) {
            iter (&id, candi[i]) ST.update (2 * id - i, n, a[i] + a[id]);
            iter (&id, queries[i]) Ans[id.se] = ST.get(i, id.fs);
        }
        rep (i, 1, Q) cout << Ans[i] <<"\n";
    }
}

void solution () {
    cin >> n;
    rep (i, 1, n) cin >> a[i];
    cin >> Q;
    rep (i, 1, Q) {
        cin >> qr[i].fs >> qr[i].se;
    }
    if (Q == 1 && qr[1].fs == 1 && qr[1].se == n) sub3 :: solution();
    else if (n <= 5000) sub2 :: solution();
    else
        sub4 :: solution ();
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}

Compilation message (stderr)

jumps.cpp: In member function 'void Segment_Tree::build(int, int, int)':
jumps.cpp:46:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |         int mid = l + r >> 1;
      |                   ~~^~~
jumps.cpp: In member function 'void Segment_Tree::update(int, int, int, int, int, long long int)':
jumps.cpp:70:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |         int mid = l + r >> 1;
      |                   ~~^~~
jumps.cpp: In member function 'long long int Segment_Tree::get(int, int, int, int, int)':
jumps.cpp:80:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         int mid = l + r >> 1;
      |                   ~~^~~
jumps.cpp: In function 'void sub2::solution()':
jumps.cpp:135:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  135 |                 int mid = j + i >> 1;
      |                           ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54