oj.uz

Submission #916489

# Submission time Handle Problem Language Result Execution time Memory
916489 2024-01-26T02:11:44 Z 12345678 Triple Jump (JOI19_jumps) C++17
100 / 100
 808 ms 91096 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int nx=5e5+5;
int n, a[nx], res[nx], q, l, r, id;
stack<int> s;
vector<int> d[nx];
vector<pair<int, int>> qrs[nx];

struct segtree
{
    int d[4*nx], lz[4*nx], omx[4*nx];
    void build(int l, int r, int i)
    {
        if (l==r) return d[i]=a[l], omx[i]=a[l], void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=max(d[2*i], d[2*i+1]);
        omx[i]=max(omx[2*i], omx[2*i+1]);
    }
    void pushlz(int l, int r, int i)
    {
        if (lz[i]==0) return void();
        d[i]=max(d[i], omx[i]+lz[i]);
        if (l!=r) lz[2*i]=max(lz[2*i], lz[i]), lz[2*i+1]=max(lz[2*i+1], lz[i]);
    }
    void update(int l, int r, int i, int ql, int qr, int vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return lz[i]=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr, vl);
        update(md+1, r ,2*i+1, ql, qr, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return -1e9;
        if (ql<=l&&r<=qr) return (lz[i]==0)?-1e9:d[i];
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
    void show(int l, int r, int i)
    {
        pushlz(l, r, i);
        cout<<l<<' '<<r<<' '<<d[i]<<'\n';
        if (l==r) return;
        int md=(l+r)/2;
        show(l, md, 2*i);
        show(md+1, r, 2*i+1);
    }
} st;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    id=n;
    for (int i=1; i<=n; i++) cin>>a[i];
    st.build(1, n, 1);
    for (int i=1; i<=n; i++)
    {
        while (!s.empty()&&a[s.top()]<=a[i]) d[s.top()].push_back(i), s.pop();
        if (!s.empty()) d[s.top()].push_back(i);
        s.push(i);
    }
    cin>>q;
    for (int i=1; i<=q; i++) cin>>l>>r, qrs[l].push_back({r, i});
    for (int i=n; i>=1; i--)
    {
        for (auto x:d[i]) if (2*x-i<=n) id=min(id, 2*x-i), st.update(1, n, 1, 2*x-i, n, a[x]+a[i]);// st.show(1, n, 1), cout<<'\n';
        for (auto [r, idx]:qrs[i]) res[idx]=st.query(1, n, 1, id, r);// cout<<"query "<<i<<' '<<r<<' '<<res[idx]<<'\n';
    }
    for (int i=1; i<=q; i++) cout<<res[i]<<'\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29016 KB Output is correct
2 Correct 7 ms 29020 KB Output is correct
3 Correct 9 ms 29020 KB Output is correct
4 Correct 8 ms 29020 KB Output is correct
5 Correct 8 ms 29216 KB Output is correct
6 Correct 9 ms 29020 KB Output is correct
7 Correct 8 ms 29020 KB Output is correct
8 Correct 8 ms 29020 KB Output is correct
9 Correct 8 ms 29020 KB Output is correct
10 Correct 8 ms 29192 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29016 KB Output is correct
2 Correct 7 ms 29020 KB Output is correct
3 Correct 9 ms 29020 KB Output is correct
4 Correct 8 ms 29020 KB Output is correct
5 Correct 8 ms 29216 KB Output is correct
6 Correct 9 ms 29020 KB Output is correct
7 Correct 8 ms 29020 KB Output is correct
8 Correct 8 ms 29020 KB Output is correct
9 Correct 8 ms 29020 KB Output is correct
10 Correct 8 ms 29192 KB Output is correct
11 Correct 196 ms 45988 KB Output is correct
12 Correct 194 ms 46084 KB Output is correct
13 Correct 222 ms 46164 KB Output is correct
14 Correct 196 ms 46076 KB Output is correct
15 Correct 211 ms 46068 KB Output is correct
16 Correct 200 ms 45312 KB Output is correct
17 Correct 224 ms 45484 KB Output is correct
18 Correct 209 ms 45368 KB Output is correct
19 Correct 197 ms 45948 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 44488 KB Output is correct
2 Correct 68 ms 43592 KB Output is correct
3 Correct 67 ms 44508 KB Output is correct
4 Correct 137 ms 43952 KB Output is correct
5 Correct 116 ms 43852 KB Output is correct
6 Correct 113 ms 43348 KB Output is correct
7 Correct 114 ms 43108 KB Output is correct
8 Correct 116 ms 43244 KB Output is correct
9 Correct 118 ms 43520 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29016 KB Output is correct
2 Correct 7 ms 29020 KB Output is correct
3 Correct 9 ms 29020 KB Output is correct
4 Correct 8 ms 29020 KB Output is correct
5 Correct 8 ms 29216 KB Output is correct
6 Correct 9 ms 29020 KB Output is correct
7 Correct 8 ms 29020 KB Output is correct
8 Correct 8 ms 29020 KB Output is correct
9 Correct 8 ms 29020 KB Output is correct
10 Correct 8 ms 29192 KB Output is correct
11 Correct 196 ms 45988 KB Output is correct
12 Correct 194 ms 46084 KB Output is correct
13 Correct 222 ms 46164 KB Output is correct
14 Correct 196 ms 46076 KB Output is correct
15 Correct 211 ms 46068 KB Output is correct
16 Correct 200 ms 45312 KB Output is correct
17 Correct 224 ms 45484 KB Output is correct
18 Correct 209 ms 45368 KB Output is correct
19 Correct 197 ms 45948 KB Output is correct
20 Correct 123 ms 44488 KB Output is correct
21 Correct 68 ms 43592 KB Output is correct
22 Correct 67 ms 44508 KB Output is correct
23 Correct 137 ms 43952 KB Output is correct
24 Correct 116 ms 43852 KB Output is correct
25 Correct 113 ms 43348 KB Output is correct
26 Correct 114 ms 43108 KB Output is correct
27 Correct 116 ms 43244 KB Output is correct
28 Correct 118 ms 43520 KB Output is correct
29 Correct 780 ms 85076 KB Output is correct
30 Correct 643 ms 84564 KB Output is correct
31 Correct 675 ms 86524 KB Output is correct
32 Correct 753 ms 85076 KB Output is correct
33 Correct 781 ms 85252 KB Output is correct
34 Correct 788 ms 83160 KB Output is correct
35 Correct 786 ms 82752 KB Output is correct
36 Correct 808 ms 82620 KB Output is correct
37 Correct 769 ms 84012 KB Output is correct
38 Correct 527 ms 90864 KB Output is correct
39 Correct 533 ms 91096 KB Output is correct
40 Correct 551 ms 87636 KB Output is correct
41 Correct 514 ms 87124 KB Output is correct
42 Correct 518 ms 87012 KB Output is correct
43 Correct 520 ms 88676 KB Output is correct
44 Correct 574 ms 90080 KB Output is correct
45 Correct 607 ms 90160 KB Output is correct
46 Correct 589 ms 87140 KB Output is correct
47 Correct 567 ms 86820 KB Output is correct
48 Correct 553 ms 86612 KB Output is correct
49 Correct 545 ms 88648 KB Output is correct
50 Correct 630 ms 88448 KB Output is correct
51 Correct 678 ms 88608 KB Output is correct
52 Correct 637 ms 85816 KB Output is correct
53 Correct 659 ms 85488 KB Output is correct
54 Correct 635 ms 85620 KB Output is correct
55 Correct 638 ms 87100 KB Output is correct