oj.uz

Submission #876244

# Submission time Handle Problem Language Result Execution time Memory
876244 2023-11-21T13:13:11 Z justinlgl20 Triple Jump (JOI19_jumps) C++14
100 / 100
 977 ms 351028 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
#define all(x) (x).begin(), (x).end()
 
template<template<typename> class Container, typename G>
ostream& operator<<(ostream& os, Container<G> x) {
    int f = 0; os << '{'; for (auto &i: x) os << (f++ ? ", " : ""), os << i; os << "}";
    return os;
}
 
void _print() {cerr << "]\n";}
 
template<typename T, typename... V>
void _print(T t, V... v) {cerr << t; if (sizeof...(v)) cerr <<", "; _print(v...);}
 
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

#define pii pair<int, int>
#define f first
#define s second

int scan() {
    int x; cin >> x; return x;
}

struct node {
    int l, r, val;
    node() {
        this->l = 0;
        this->r = 0;
        this->val = 0;
    }
    node(int a, int b, int v) {
        this->l = a; this->r = b; this->val = v;
    }
};

node merge(node a, node b) {
    return node(max(a.l, b.l), max(b.r, a.r), max({a.val, b.val, a.l+b.r}));
}

int n, q;

int value[5000005];

struct seg {
    vector<node> T;
    int n;
    seg(int n) {
        this->n = n;
        T.resize(2*n+5);
        for (int i = 0; i < 2*n; i++) T[i] = node(0, 0, 0);
        for (int i = 0; i <= n; i++) {
            T[i|n].r = T[i|n].val = value[i];
        }
        for (int i = n-1; i; i--) {
            T[i] = merge(T[i<<1], T[i<<1|1]);
        }
    }

    void upd(int x, int v) {
        x |= n;
        T[x].val = max(T[x].l, v)+T[x].r;
        T[x].l = max(T[x].l, v);
        while (x >>= 1) T[x] = merge(T[x<<1], T[x<<1|1]);
    }

    int query(int ql, int qr) {
        node l= node(0, 0, 0);
        node r = node(0, 0, 0);
        ql |= n; qr |= n;
        while (ql <= qr) {
            if (ql&1) l = merge(l, T[ql++]);
            if (~qr &1) r = merge(T[qr--], r);
            ql>>=1;
            qr>>=1;
        }
        return (merge(l, r)).val;
    }
};

seg *segtree;

vector<pii> queries[5000005];
vector<pii> updates[5000005];

int32_t main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> value[i];
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int l, r; cin >> l >> r;
        queries[l].emplace_back(r, i);
    }

    segtree = new seg(1048576);
    stack<int> stck;
    dbg("...");
    for (int i = 1; i <= n; i++) {
        while (stck.size()) {
            int j = stck.top();
            if (value[i] > value[j]) {
                stck.pop();
                updates[j].emplace_back(i, value[i]+value[j]);
            } else {
                updates[j].emplace_back(i, value[i]+value[j]);
                break;
            }

            
        }
        stck.push(i);
    }
    vector<int> ans(q+3, 0);
    for (int i = n; i > 0; i--) {
        for (auto j : updates[i]) {
            if ((int)2*j.f - i <= n) segtree->upd((int)2*j.f-i, j.s);
        }
        for (auto j : queries[i]) {
            ans[j.s] = segtree->query(i, j.f);
        }
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 285776 KB Output is correct
2 Correct 76 ms 285892 KB Output is correct
3 Correct 83 ms 285776 KB Output is correct
4 Correct 75 ms 285860 KB Output is correct
5 Correct 74 ms 285776 KB Output is correct
6 Correct 74 ms 285624 KB Output is correct
7 Correct 74 ms 285856 KB Output is correct
8 Correct 76 ms 285784 KB Output is correct
9 Correct 75 ms 285780 KB Output is correct
10 Correct 74 ms 285684 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 285776 KB Output is correct
2 Correct 76 ms 285892 KB Output is correct
3 Correct 83 ms 285776 KB Output is correct
4 Correct 75 ms 285860 KB Output is correct
5 Correct 74 ms 285776 KB Output is correct
6 Correct 74 ms 285624 KB Output is correct
7 Correct 74 ms 285856 KB Output is correct
8 Correct 76 ms 285784 KB Output is correct
9 Correct 75 ms 285780 KB Output is correct
10 Correct 74 ms 285684 KB Output is correct
11 Correct 349 ms 312876 KB Output is correct
12 Correct 355 ms 312932 KB Output is correct
13 Correct 347 ms 312836 KB Output is correct
14 Correct 358 ms 312660 KB Output is correct
15 Correct 350 ms 312856 KB Output is correct
16 Correct 356 ms 312248 KB Output is correct
17 Correct 359 ms 312288 KB Output is correct
18 Correct 357 ms 311888 KB Output is correct
19 Correct 357 ms 312632 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 299904 KB Output is correct
2 Correct 179 ms 295812 KB Output is correct
3 Correct 183 ms 297544 KB Output is correct
4 Correct 257 ms 300168 KB Output is correct
5 Correct 241 ms 299860 KB Output is correct
6 Correct 224 ms 299264 KB Output is correct
7 Correct 221 ms 299092 KB Output is correct
8 Correct 224 ms 299044 KB Output is correct
9 Correct 228 ms 299348 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 285776 KB Output is correct
2 Correct 76 ms 285892 KB Output is correct
3 Correct 83 ms 285776 KB Output is correct
4 Correct 75 ms 285860 KB Output is correct
5 Correct 74 ms 285776 KB Output is correct
6 Correct 74 ms 285624 KB Output is correct
7 Correct 74 ms 285856 KB Output is correct
8 Correct 76 ms 285784 KB Output is correct
9 Correct 75 ms 285780 KB Output is correct
10 Correct 74 ms 285684 KB Output is correct
11 Correct 349 ms 312876 KB Output is correct
12 Correct 355 ms 312932 KB Output is correct
13 Correct 347 ms 312836 KB Output is correct
14 Correct 358 ms 312660 KB Output is correct
15 Correct 350 ms 312856 KB Output is correct
16 Correct 356 ms 312248 KB Output is correct
17 Correct 359 ms 312288 KB Output is correct
18 Correct 357 ms 311888 KB Output is correct
19 Correct 357 ms 312632 KB Output is correct
20 Correct 239 ms 299904 KB Output is correct
21 Correct 179 ms 295812 KB Output is correct
22 Correct 183 ms 297544 KB Output is correct
23 Correct 257 ms 300168 KB Output is correct
24 Correct 241 ms 299860 KB Output is correct
25 Correct 224 ms 299264 KB Output is correct
26 Correct 221 ms 299092 KB Output is correct
27 Correct 224 ms 299044 KB Output is correct
28 Correct 228 ms 299348 KB Output is correct
29 Correct 964 ms 348500 KB Output is correct
30 Correct 833 ms 338644 KB Output is correct
31 Correct 829 ms 342776 KB Output is correct
32 Correct 967 ms 348452 KB Output is correct
33 Correct 977 ms 348756 KB Output is correct
34 Correct 923 ms 346300 KB Output is correct
35 Correct 947 ms 345804 KB Output is correct
36 Correct 920 ms 345796 KB Output is correct
37 Correct 953 ms 347220 KB Output is correct
38 Correct 812 ms 351020 KB Output is correct
39 Correct 809 ms 351028 KB Output is correct
40 Correct 772 ms 347672 KB Output is correct
41 Correct 793 ms 347176 KB Output is correct
42 Correct 767 ms 347348 KB Output is correct
43 Correct 796 ms 349012 KB Output is correct
44 Correct 851 ms 350800 KB Output is correct
45 Correct 860 ms 350900 KB Output is correct
46 Correct 809 ms 347732 KB Output is correct
47 Correct 811 ms 347404 KB Output is correct
48 Correct 801 ms 347304 KB Output is correct
49 Correct 830 ms 349288 KB Output is correct
50 Correct 903 ms 350116 KB Output is correct
51 Correct 934 ms 350108 KB Output is correct
52 Correct 865 ms 347656 KB Output is correct
53 Correct 878 ms 347344 KB Output is correct
54 Correct 881 ms 347472 KB Output is correct
55 Correct 896 ms 349016 KB Output is correct