oj.uz

Submission #967573

# Submission time Handle Problem Language Result Execution time Memory
967573 2024-04-22T13:00:35 Z vjudge1 Triple Jump (JOI19_jumps) C++17
100 / 100
 868 ms 62916 KB 
#include <bits/stdc++.h>

#define ll long long
#define all(x) x.begin(), x.end()
#define Neco "Triple Jump"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 5e5 + 7

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rng);
}

int n, Q;
int q[maxn], top;
struct dl { int l, r, id; } qr[maxn];
vector<pair<int, int>> P;
ll a[maxn], nex[2 * maxn], ans[maxn];

struct IT {
    struct Node {
        ll Le, Ri, All;
    } st[4 * maxn];

    Node cb(Node x, Node y) {
        Node P;
        P.Le = max(x.Le, y.Le);
        P.Ri = max(x.Ri, y.Ri);
        P.All = max({x.All, y.All, x.Le + y.Ri});

        return P;
    }

    void update(int x, int val, int id = 1, int l = 1, int r = n)
    {
        if(l > x || r < x) return ;
        if(l == r) {
            st[id].Le = val, st[id].Ri = a[l];
            st[id].All = st[id].Le + st[id].Ri;
            return ;
        }

        int mid = (l + r) >> 1;
        update(x, val, _left), update(x, val, _right);

        st[id] = cb(st[id * 2], st[id * 2 + 1]);
    }

    Node get(int u, int v, int id = 1, int l = 1, int r = n)
    {
        if(l > v || r < u) return {0, 0, 0};
        if(u <= l && r <= v) return st[id];

        int mid = (l + r) >> 1;
        return cb(get(u, v, _left), get(u, v, _right));
    }
} St;


void solve()
{

    cin >> n ;
    fi(i, 1, n) cin >> a[i];
    cin >> Q;
    fi(i, 1, Q) cin >> qr[i].l >> qr[i].r, qr[i].id = i;

    fi(i, 1, n) {
        while(top && a[i] >= a[q[top]]) P.push_back({q[top], i}), --top;
        if(top) P.push_back({q[top], i}); q[++top] = i;
    }

    sort(all(P), [](pair<int, int> x, pair<int, int> y) { return x.first < y.first; } );

    for(int i = P.size() - 1; i >= 0; -- i) {
        int u, v, id, val; tie(u, v) = P[i];
        id = v * 2 - u, val = St.get(id, id).Le;

        nex[i] = val, St.update(id, max(1ll * val, a[u] + a[v]));
    }

    sort(qr + 1, qr + 1 + Q, [](dl x, dl y) { return x.l < y.l; } );

    int j = 0;
    fi(i, 1, Q) {
        while(P[j].first < qr[i].l) {
            St.update(2 * P[j].second - P[j].first, nex[j]);
            ++j;
        }

        ans[qr[i].id] = St.get(qr[i].l, qr[i].r).All;
    }

    fi(i, 1, Q) cout << ans[i] << '\n';


}


int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }


    int nTest = 1;
//    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message

jumps.cpp: In function 'void solve()':
jumps.cpp:83:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   83 |         if(top) P.push_back({q[top], i}); q[++top] = i;
      |         ^~
jumps.cpp:83:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   83 |         if(top) P.push_back({q[top], i}); q[++top] = i;
      |                                           ^
jumps.cpp: In function 'int main()':
jumps.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8612 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8612 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 210 ms 22488 KB Output is correct
12 Correct 206 ms 22096 KB Output is correct
13 Correct 203 ms 22220 KB Output is correct
14 Correct 201 ms 22352 KB Output is correct
15 Correct 203 ms 22488 KB Output is correct
16 Correct 206 ms 21668 KB Output is correct
17 Correct 214 ms 22052 KB Output is correct
18 Correct 206 ms 21588 KB Output is correct
19 Correct 221 ms 22256 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 30912 KB Output is correct
2 Correct 75 ms 26568 KB Output is correct
3 Correct 76 ms 27336 KB Output is correct
4 Correct 139 ms 31340 KB Output is correct
5 Correct 133 ms 30400 KB Output is correct
6 Correct 131 ms 30396 KB Output is correct
7 Correct 131 ms 30332 KB Output is correct
8 Correct 134 ms 31472 KB Output is correct
9 Correct 130 ms 30236 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8612 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 210 ms 22488 KB Output is correct
12 Correct 206 ms 22096 KB Output is correct
13 Correct 203 ms 22220 KB Output is correct
14 Correct 201 ms 22352 KB Output is correct
15 Correct 203 ms 22488 KB Output is correct
16 Correct 206 ms 21668 KB Output is correct
17 Correct 214 ms 22052 KB Output is correct
18 Correct 206 ms 21588 KB Output is correct
19 Correct 221 ms 22256 KB Output is correct
20 Correct 132 ms 30912 KB Output is correct
21 Correct 75 ms 26568 KB Output is correct
22 Correct 76 ms 27336 KB Output is correct
23 Correct 139 ms 31340 KB Output is correct
24 Correct 133 ms 30400 KB Output is correct
25 Correct 131 ms 30396 KB Output is correct
26 Correct 131 ms 30332 KB Output is correct
27 Correct 134 ms 31472 KB Output is correct
28 Correct 130 ms 30236 KB Output is correct
29 Correct 868 ms 62772 KB Output is correct
30 Correct 609 ms 56584 KB Output is correct
31 Correct 638 ms 57168 KB Output is correct
32 Correct 839 ms 62644 KB Output is correct
33 Correct 852 ms 62856 KB Output is correct
34 Correct 816 ms 61880 KB Output is correct
35 Correct 836 ms 61880 KB Output is correct
36 Correct 823 ms 61876 KB Output is correct
37 Correct 847 ms 62916 KB Output is correct
38 Correct 708 ms 62640 KB Output is correct
39 Correct 708 ms 62592 KB Output is correct
40 Correct 731 ms 60996 KB Output is correct
41 Correct 703 ms 60592 KB Output is correct
42 Correct 718 ms 60896 KB Output is correct
43 Correct 727 ms 61444 KB Output is correct
44 Correct 723 ms 62772 KB Output is correct
45 Correct 752 ms 62536 KB Output is correct
46 Correct 775 ms 61132 KB Output is correct
47 Correct 787 ms 61368 KB Output is correct
48 Correct 724 ms 60976 KB Output is correct
49 Correct 715 ms 62224 KB Output is correct
50 Correct 741 ms 62608 KB Output is correct
51 Correct 735 ms 62512 KB Output is correct
52 Correct 767 ms 62032 KB Output is correct
53 Correct 744 ms 61700 KB Output is correct
54 Correct 735 ms 61884 KB Output is correct
55 Correct 791 ms 62536 KB Output is correct