oj.uz

Submission #1084779

# Submission time Handle Problem Language Result Execution time Memory
1084779 2024-09-07T01:16:11 Z underwaterkillerwhale Triple Jump (JOI19_jumps) C++17
100 / 100
 782 ms 331916 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";
        }
    }
}

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

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 10 ms 23900 KB Output is correct
2 Correct 131 ms 318144 KB Output is correct
3 Correct 131 ms 318288 KB Output is correct
4 Correct 131 ms 318140 KB Output is correct
5 Correct 142 ms 318108 KB Output is correct
6 Correct 131 ms 318228 KB Output is correct
7 Correct 139 ms 318304 KB Output is correct
8 Correct 130 ms 318292 KB Output is correct
9 Correct 140 ms 318288 KB Output is correct
10 Correct 158 ms 318288 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 131 ms 318144 KB Output is correct
3 Correct 131 ms 318288 KB Output is correct
4 Correct 131 ms 318140 KB Output is correct
5 Correct 142 ms 318108 KB Output is correct
6 Correct 131 ms 318228 KB Output is correct
7 Correct 139 ms 318304 KB Output is correct
8 Correct 130 ms 318292 KB Output is correct
9 Correct 140 ms 318288 KB Output is correct
10 Correct 158 ms 318288 KB Output is correct
11 Correct 299 ms 331784 KB Output is correct
12 Correct 303 ms 331860 KB Output is correct
13 Correct 303 ms 331868 KB Output is correct
14 Correct 305 ms 331848 KB Output is correct
15 Correct 314 ms 331916 KB Output is correct
16 Correct 302 ms 331092 KB Output is correct
17 Correct 317 ms 331160 KB Output is correct
18 Correct 339 ms 331092 KB Output is correct
19 Correct 318 ms 331640 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 45728 KB Output is correct
2 Correct 76 ms 43468 KB Output is correct
3 Correct 79 ms 44828 KB Output is correct
4 Correct 111 ms 45712 KB Output is correct
5 Correct 109 ms 45588 KB Output is correct
6 Correct 104 ms 45096 KB Output is correct
7 Correct 113 ms 44744 KB Output is correct
8 Correct 105 ms 45012 KB Output is correct
9 Correct 128 ms 45324 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 131 ms 318144 KB Output is correct
3 Correct 131 ms 318288 KB Output is correct
4 Correct 131 ms 318140 KB Output is correct
5 Correct 142 ms 318108 KB Output is correct
6 Correct 131 ms 318228 KB Output is correct
7 Correct 139 ms 318304 KB Output is correct
8 Correct 130 ms 318292 KB Output is correct
9 Correct 140 ms 318288 KB Output is correct
10 Correct 158 ms 318288 KB Output is correct
11 Correct 299 ms 331784 KB Output is correct
12 Correct 303 ms 331860 KB Output is correct
13 Correct 303 ms 331868 KB Output is correct
14 Correct 305 ms 331848 KB Output is correct
15 Correct 314 ms 331916 KB Output is correct
16 Correct 302 ms 331092 KB Output is correct
17 Correct 317 ms 331160 KB Output is correct
18 Correct 339 ms 331092 KB Output is correct
19 Correct 318 ms 331640 KB Output is correct
20 Correct 108 ms 45728 KB Output is correct
21 Correct 76 ms 43468 KB Output is correct
22 Correct 79 ms 44828 KB Output is correct
23 Correct 111 ms 45712 KB Output is correct
24 Correct 109 ms 45588 KB Output is correct
25 Correct 104 ms 45096 KB Output is correct
26 Correct 113 ms 44744 KB Output is correct
27 Correct 105 ms 45012 KB Output is correct
28 Correct 128 ms 45324 KB Output is correct
29 Correct 710 ms 109708 KB Output is correct
30 Correct 594 ms 108936 KB Output is correct
31 Correct 622 ms 113308 KB Output is correct
32 Correct 709 ms 109720 KB Output is correct
33 Correct 742 ms 109736 KB Output is correct
34 Correct 736 ms 107656 KB Output is correct
35 Correct 782 ms 107084 KB Output is correct
36 Correct 699 ms 107088 KB Output is correct
37 Correct 706 ms 108528 KB Output is correct
38 Correct 558 ms 115360 KB Output is correct
39 Correct 549 ms 115488 KB Output is correct
40 Correct 538 ms 112140 KB Output is correct
41 Correct 510 ms 111536 KB Output is correct
42 Correct 530 ms 111500 KB Output is correct
43 Correct 618 ms 113264 KB Output is correct
44 Correct 573 ms 114792 KB Output is correct
45 Correct 565 ms 115024 KB Output is correct
46 Correct 570 ms 111724 KB Output is correct
47 Correct 537 ms 111188 KB Output is correct
48 Correct 541 ms 111188 KB Output is correct
49 Correct 545 ms 113488 KB Output is correct
50 Correct 612 ms 113292 KB Output is correct
51 Correct 614 ms 112980 KB Output is correct
52 Correct 610 ms 110464 KB Output is correct
53 Correct 607 ms 110160 KB Output is correct
54 Correct 589 ms 110204 KB Output is correct
55 Correct 604 ms 111880 KB Output is correct