oj.uz

Submission #1084776

# Submission time Handle Problem Language Result Execution time Memory
1084776 2024-09-07T01:10:20 Z underwaterkillerwhale Triple Jump (JOI19_jumps) C++17
46 / 100
 296 ms 308404 KB 
#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";
        }
    }

}

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();

}

#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 120 ms 294676 KB Output is correct
3 Correct 115 ms 294808 KB Output is correct
4 Correct 115 ms 294740 KB Output is correct
5 Correct 115 ms 294736 KB Output is correct
6 Correct 115 ms 294740 KB Output is correct
7 Correct 115 ms 294736 KB Output is correct
8 Correct 115 ms 294708 KB Output is correct
9 Correct 115 ms 294736 KB Output is correct
10 Correct 119 ms 294824 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 120 ms 294676 KB Output is correct
3 Correct 115 ms 294808 KB Output is correct
4 Correct 115 ms 294740 KB Output is correct
5 Correct 115 ms 294736 KB Output is correct
6 Correct 115 ms 294740 KB Output is correct
7 Correct 115 ms 294736 KB Output is correct
8 Correct 115 ms 294708 KB Output is correct
9 Correct 115 ms 294736 KB Output is correct
10 Correct 119 ms 294824 KB Output is correct
11 Correct 276 ms 308404 KB Output is correct
12 Correct 296 ms 308304 KB Output is correct
13 Correct 273 ms 308344 KB Output is correct
14 Correct 286 ms 308356 KB Output is correct
15 Correct 287 ms 308308 KB Output is correct
16 Correct 269 ms 307796 KB Output is correct
17 Correct 277 ms 307680 KB Output is correct
18 Correct 268 ms 307796 KB Output is correct
19 Correct 272 ms 308312 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 22228 KB Output is correct
2 Correct 55 ms 19928 KB Output is correct
3 Correct 61 ms 21360 KB Output is correct
4 Correct 96 ms 22228 KB Output is correct
5 Correct 101 ms 22216 KB Output is correct
6 Correct 90 ms 21460 KB Output is correct
7 Correct 89 ms 21444 KB Output is correct
8 Correct 89 ms 21452 KB Output is correct
9 Correct 89 ms 21704 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 120 ms 294676 KB Output is correct
3 Correct 115 ms 294808 KB Output is correct
4 Correct 115 ms 294740 KB Output is correct
5 Correct 115 ms 294736 KB Output is correct
6 Correct 115 ms 294740 KB Output is correct
7 Correct 115 ms 294736 KB Output is correct
8 Correct 115 ms 294708 KB Output is correct
9 Correct 115 ms 294736 KB Output is correct
10 Correct 119 ms 294824 KB Output is correct
11 Correct 276 ms 308404 KB Output is correct
12 Correct 296 ms 308304 KB Output is correct
13 Correct 273 ms 308344 KB Output is correct
14 Correct 286 ms 308356 KB Output is correct
15 Correct 287 ms 308308 KB Output is correct
16 Correct 269 ms 307796 KB Output is correct
17 Correct 277 ms 307680 KB Output is correct
18 Correct 268 ms 307796 KB Output is correct
19 Correct 272 ms 308312 KB Output is correct
20 Correct 93 ms 22228 KB Output is correct
21 Correct 55 ms 19928 KB Output is correct
22 Correct 61 ms 21360 KB Output is correct
23 Correct 96 ms 22228 KB Output is correct
24 Correct 101 ms 22216 KB Output is correct
25 Correct 90 ms 21460 KB Output is correct
26 Correct 89 ms 21444 KB Output is correct
27 Correct 89 ms 21452 KB Output is correct
28 Correct 89 ms 21704 KB Output is correct
29 Incorrect 84 ms 17236 KB Output isn't correct
30 Halted 0 ms 0 KB -