oj.uz

Submission #878666

# Submission time Handle Problem Language Result Execution time Memory
878666 2023-11-25T04:00:46 Z vjudge1 Triple Jump (JOI19_jumps) C++17
100 / 100
 777 ms 51520 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()

void init()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ///freopen(TASKNAME".INP","r",stdin); freopen(TASKNAME".OUT","w",stdout);
}

#define TASKNAME "NAME"

const int SZ = 5e5+5;
const ll INF = INT_MAX / 2, MOD = 1e9+7, INFLL = 2e18;
const double epsilon = 1e-3;

int n, a[SZ], q, res[SZ];

struct Query
{
    int lo, hi, id;
    Query(int _lo = 0, int _hi = 0, int _id = 0) : lo(_lo), hi(_hi), id(_id) {}

    bool operator < (const Query& other) const
    {
        return lo > other.lo;
    }
};

Query b[SZ];
stack<int> st;

struct SegTree
{
    struct Node
    {
        int mx1, mx2, lazy;
        Node(int _mx1 = 0, int _mx2 = 0, int _lazy = 0) : mx1(_mx1), mx2(_mx2), lazy(_lazy) {}

        Node operator + (const Node& other) const
        {
            return { max(mx1, other.mx1), max(mx2, other.mx2), 0 };
        }
    } nodes[4*SZ];

    void build(int id, int lo, int hi)
    {
        if(lo == hi)
        {
            nodes[id] = {a[lo],a[lo], 0};
            return;
        }
        int mid = (lo + hi) / 2;
        build(2*id, lo, mid);
        build(2*id+1, mid+1, hi);
        nodes[id] = nodes[2*id] + nodes[2*id+1];
    }

    void down(int id, int lo, int hi)
    {
        int t = nodes[id].lazy;
        nodes[2*id].mx1 = max(nodes[2*id].mx1, nodes[2*id].mx2 + t);
        nodes[2*id].lazy = max(nodes[2*id].lazy, t);
        nodes[2*id+1].mx1 = max(nodes[2*id+1].mx1, nodes[2*id+1].mx2 + t);
        nodes[2*id+1].lazy = max(nodes[2*id+1].lazy, t);
        nodes[id].lazy = 0;
    }

    int u, v, val;

    void updateR(int id, int lo, int hi)
    {
        if(lo > v || hi < u) return;
        if(lo >= u && hi <= v)
        {
            nodes[id].mx1 = max(nodes[id].mx1, nodes[id].mx2 + val);
            nodes[id].lazy = max(nodes[id].lazy, val);
            return;
        }
        down(id, lo, hi);
        int mid = (lo + hi) / 2;
        updateR(2*id, lo, mid);
        updateR(2*id+1, mid+1, hi);
        nodes[id] = nodes[2*id] + nodes[2*id+1];
    }

    void update(int u, int v, int val)
    {
        if(u > v) return;
        SegTree::u = u;
        SegTree::v = v;
        SegTree::val = val;
        updateR(1, 1, n);
    }

    Node queryR(int id, int lo, int hi)
    {
        if(lo > v || hi < u) return {0,0,0};
        if(lo >= u && hi <= v) return nodes[id];
        down(id, lo, hi);
        int mid = (lo + hi) / 2;
        return queryR(2*id, lo, mid) + queryR(2*id+1, mid+1, hi);
    }

    Node query(int u, int v)
    {
        if(u > v) return {0,0,0};
        SegTree::u = u;
        SegTree::v = v;
        return queryR(1, 1, n);
    }
} seg;

int main()
{
    init();
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    cin >> q;
    for(int i = 1; i <= q; i++)
    {
        int lo,hi;
        cin >> lo >> hi;
        b[i] = {lo,hi,i};
    }
    sort(b + 1, b + q + 1);
    int j = n;
    seg.build(1, 1, n);
    for(int i = 1; i <= q; i++)
    {
        int lo = b[i].lo, hi = b[i].hi, id = b[i].id;
        //cout << lo << " - " << hi << '\n';
        while(j >= lo)
        {
            while(!st.empty())
            {
                int x = st.top();
                seg.update(x + x - j, n, a[j] + a[x]);
                if(a[x] >= a[j]) break;
                st.pop();
            }
            st.push(j);
            j--;
        }
        res[id] = seg.query(lo, hi).mx1;
    }
    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 33372 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 6 ms 33372 KB Output is correct
4 Correct 6 ms 33372 KB Output is correct
5 Correct 6 ms 33372 KB Output is correct
6 Correct 6 ms 33468 KB Output is correct
7 Correct 6 ms 33372 KB Output is correct
8 Correct 6 ms 33376 KB Output is correct
9 Correct 6 ms 33412 KB Output is correct
10 Correct 6 ms 33416 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33372 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 6 ms 33372 KB Output is correct
4 Correct 6 ms 33372 KB Output is correct
5 Correct 6 ms 33372 KB Output is correct
6 Correct 6 ms 33468 KB Output is correct
7 Correct 6 ms 33372 KB Output is correct
8 Correct 6 ms 33376 KB Output is correct
9 Correct 6 ms 33412 KB Output is correct
10 Correct 6 ms 33416 KB Output is correct
11 Correct 293 ms 43032 KB Output is correct
12 Correct 292 ms 43100 KB Output is correct
13 Correct 301 ms 43040 KB Output is correct
14 Correct 285 ms 43040 KB Output is correct
15 Correct 291 ms 43092 KB Output is correct
16 Correct 292 ms 42656 KB Output is correct
17 Correct 292 ms 42324 KB Output is correct
18 Correct 304 ms 42244 KB Output is correct
19 Correct 286 ms 42836 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 35164 KB Output is correct
2 Correct 58 ms 35924 KB Output is correct
3 Correct 57 ms 35164 KB Output is correct
4 Correct 102 ms 35188 KB Output is correct
5 Correct 102 ms 35156 KB Output is correct
6 Correct 98 ms 34524 KB Output is correct
7 Correct 98 ms 34428 KB Output is correct
8 Correct 101 ms 34396 KB Output is correct
9 Correct 114 ms 34756 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33372 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 6 ms 33372 KB Output is correct
4 Correct 6 ms 33372 KB Output is correct
5 Correct 6 ms 33372 KB Output is correct
6 Correct 6 ms 33468 KB Output is correct
7 Correct 6 ms 33372 KB Output is correct
8 Correct 6 ms 33376 KB Output is correct
9 Correct 6 ms 33412 KB Output is correct
10 Correct 6 ms 33416 KB Output is correct
11 Correct 293 ms 43032 KB Output is correct
12 Correct 292 ms 43100 KB Output is correct
13 Correct 301 ms 43040 KB Output is correct
14 Correct 285 ms 43040 KB Output is correct
15 Correct 291 ms 43092 KB Output is correct
16 Correct 292 ms 42656 KB Output is correct
17 Correct 292 ms 42324 KB Output is correct
18 Correct 304 ms 42244 KB Output is correct
19 Correct 286 ms 42836 KB Output is correct
20 Correct 106 ms 35164 KB Output is correct
21 Correct 58 ms 35924 KB Output is correct
22 Correct 57 ms 35164 KB Output is correct
23 Correct 102 ms 35188 KB Output is correct
24 Correct 102 ms 35156 KB Output is correct
25 Correct 98 ms 34524 KB Output is correct
26 Correct 98 ms 34428 KB Output is correct
27 Correct 101 ms 34396 KB Output is correct
28 Correct 114 ms 34756 KB Output is correct
29 Correct 719 ms 49692 KB Output is correct
30 Correct 618 ms 51520 KB Output is correct
31 Correct 591 ms 49580 KB Output is correct
32 Correct 713 ms 49708 KB Output is correct
33 Correct 723 ms 49556 KB Output is correct
34 Correct 727 ms 47404 KB Output is correct
35 Correct 777 ms 47020 KB Output is correct
36 Correct 738 ms 47024 KB Output is correct
37 Correct 720 ms 48496 KB Output is correct
38 Correct 608 ms 49748 KB Output is correct
39 Correct 621 ms 49564 KB Output is correct
40 Correct 598 ms 46424 KB Output is correct
41 Correct 594 ms 45868 KB Output is correct
42 Correct 602 ms 45652 KB Output is correct
43 Correct 615 ms 47404 KB Output is correct
44 Correct 629 ms 49820 KB Output is correct
45 Correct 634 ms 49564 KB Output is correct
46 Correct 629 ms 46420 KB Output is correct
47 Correct 663 ms 46140 KB Output is correct
48 Correct 613 ms 46164 KB Output is correct
49 Correct 651 ms 48368 KB Output is correct
50 Correct 661 ms 49724 KB Output is correct
51 Correct 657 ms 49704 KB Output is correct
52 Correct 651 ms 47140 KB Output is correct
53 Correct 650 ms 46952 KB Output is correct
54 Correct 686 ms 47140 KB Output is correct
55 Correct 654 ms 48584 KB Output is correct