oj.uz

Submission #711638

# Submission time Handle Problem Language Result Execution time Memory
711638 2023-03-17T10:24:19 Z Thienu Triple Jump (JOI19_jumps) C++17
100 / 100
 1865 ms 124444 KB 
#include <bits/stdc++.h>

using namespace std;

#define u_map unordered_map
#define u_set unordered_set
#define u_multiset unordered_multiset

using ll = long long;
using vvi = vector<vector<int>>;
using vi = vector<int>;
using vvll = vector<vector<long long>>;
using vll = vector<long long>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<typename C> struct rge{C l, r;};
template<typename C> rge<C> range(C i, C j) { return rge<C>{i, j}; }
template<typename C> ostream& operator<<(ostream &os, rge<C> &r) { os << '{'; for(auto it = r.l; it != r.r; it++) os << "," + (it == r.l) << *it; os << '}'; return os; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '{' << p.first << "," << p.second << '}'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ","; return os << '}'; }
void dbg_out() { cerr << ']' << endl; }
template<typename A> void dbg_out(A H) { cerr << H; dbg_out(); }
template<typename A, typename B, typename... C> void dbg_out(A H, B G, C... T) { cerr << H << ","; dbg_out(G, T...); }
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = [", dbg_out(__VA_ARGS__)
#else
#define debug(...)
#endif

const int INF = 1e9 + 7;

// range chmax(a[i] + c) (a constant)
// range max
struct Node {
    Node *l, *r;
    int lo, hi;
    int mmax = -INF;
    int vmax = -INF;
    int maxa = -INF;

    Node(int lo, int hi, vi &v) : lo(lo), hi(hi) {
        debug(lo, hi);
        if(lo + 1 == hi){
            maxa = v[lo];
        } else {
            int mid = lo + (hi - lo) / 2;
            l = new Node(lo, mid, v);
            r = new Node(mid, hi, v);
            maxa = max(l->maxa, r->maxa);
            debug("upd", lo, hi);
            update();
        }
    }

    void update(){
        debug(lo, hi, lo + 1 < hi);
        assert(lo + 1 < hi);
        vmax = max(l->vmax, r->vmax);
    }

    void push(){
        assert(lo + 1 < hi);
        if(vmax != -INF){
            l->chmax(lo, hi, mmax);
            r->chmax(lo, hi, mmax);
            mmax = -INF;
        }
    }

    // range chmax
    void chmax(int left, int right, int val) {
        debug(left, right, val);
        if(right <= lo || hi <= left) return;
        if(left <= lo && hi <= right){
            mmax = max(mmax, val);
            vmax = max(vmax, val + maxa);
        } else {
            push();
            l->chmax(left, right, val);
            r->chmax(left, right, val);
            update();
        }
    }

    // range max
    int query(int left, int right){
        debug(left, right);
        if(right <= lo || hi <= left) return -INF;
        if(left <= lo && hi <= right){
            return vmax;
        } else {
            push();
            return max(l->query(left, right), r->query(left, right));
        }
    }
};

void solve(){
    int n;
    cin >> n;
    vi v(n);
    for(int i = 0; i < n; i++) cin >> v[i];
    int q;
    cin >> q;
    vector<vpii> queries(n); // queries[x] contains {y, idx} ([x, y])
    for(int i = 0; i < q; i++){
        int x, y;
        cin >> x >> y;
        x--;y--;
        queries[x].push_back({y, i});
    }

    vi larger(n);
    stack<int> s;
    for(int i = n-1; i >= 0; i--){
        while(!s.empty() && v[s.top()] <= v[i]){
            s.pop();
        }
        if(s.empty()) larger[i] = n;
        else larger[i] = s.top();
        s.push(i);
    }
    debug(larger);
    vvi good_seg(n); // good_seg[i] contains j iff for all k, i < k < j => a[k] < min(a[i], a[j])
    for(int i = 0; i < n; i++){
        int ptr = i+1;
        while(ptr != n){
            good_seg[i].push_back(ptr);
            if(v[ptr] >= v[i]) break;
            ptr = larger[ptr];
        }
    }
    debug(good_seg);

    vi ans(q);

    Node* st = new Node(0, n, v);

    for(int t = n-1; t >= 0; t--){
        for(int r : good_seg[t]) {
            // good segment: (t, r)
            if(2 * r - t < n) {
                st->chmax(2 * r - t, n, v[t] + v[r]);
            }
        }
        for(pii p : queries[t]){
            int r, idx;
            tie(r, idx) = p;
            ans[idx] = st->query(t, r+1);
        }
    }

    for(int i : ans){
        cout << i << endl;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 328 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 812 ms 19188 KB Output is correct
12 Correct 833 ms 19056 KB Output is correct
13 Correct 858 ms 19152 KB Output is correct
14 Correct 847 ms 19220 KB Output is correct
15 Correct 830 ms 19220 KB Output is correct
16 Correct 850 ms 18488 KB Output is correct
17 Correct 908 ms 18484 KB Output is correct
18 Correct 851 ms 18408 KB Output is correct
19 Correct 880 ms 18980 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 38220 KB Output is correct
2 Correct 111 ms 38896 KB Output is correct
3 Correct 111 ms 38064 KB Output is correct
4 Correct 175 ms 38220 KB Output is correct
5 Correct 196 ms 38200 KB Output is correct
6 Correct 171 ms 37588 KB Output is correct
7 Correct 165 ms 37524 KB Output is correct
8 Correct 227 ms 37448 KB Output is correct
9 Correct 170 ms 37956 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 812 ms 19188 KB Output is correct
12 Correct 833 ms 19056 KB Output is correct
13 Correct 858 ms 19152 KB Output is correct
14 Correct 847 ms 19220 KB Output is correct
15 Correct 830 ms 19220 KB Output is correct
16 Correct 850 ms 18488 KB Output is correct
17 Correct 908 ms 18484 KB Output is correct
18 Correct 851 ms 18408 KB Output is correct
19 Correct 880 ms 18980 KB Output is correct
20 Correct 189 ms 38220 KB Output is correct
21 Correct 111 ms 38896 KB Output is correct
22 Correct 111 ms 38064 KB Output is correct
23 Correct 175 ms 38220 KB Output is correct
24 Correct 196 ms 38200 KB Output is correct
25 Correct 171 ms 37588 KB Output is correct
26 Correct 165 ms 37524 KB Output is correct
27 Correct 227 ms 37448 KB Output is correct
28 Correct 170 ms 37956 KB Output is correct
29 Correct 1865 ms 118772 KB Output is correct
30 Correct 1632 ms 120316 KB Output is correct
31 Correct 1576 ms 118084 KB Output is correct
32 Correct 1784 ms 118696 KB Output is correct
33 Correct 1848 ms 118764 KB Output is correct
34 Correct 1796 ms 116352 KB Output is correct
35 Correct 1742 ms 116080 KB Output is correct
36 Correct 1831 ms 116072 KB Output is correct
37 Correct 1767 ms 117556 KB Output is correct
38 Correct 1448 ms 124444 KB Output is correct
39 Correct 1396 ms 124324 KB Output is correct
40 Correct 1319 ms 121192 KB Output is correct
41 Correct 1338 ms 120564 KB Output is correct
42 Correct 1348 ms 120616 KB Output is correct
43 Correct 1394 ms 122332 KB Output is correct
44 Correct 1409 ms 123892 KB Output is correct
45 Correct 1418 ms 123808 KB Output is correct
46 Correct 1387 ms 120620 KB Output is correct
47 Correct 1331 ms 120220 KB Output is correct
48 Correct 1383 ms 120224 KB Output is correct
49 Correct 1394 ms 122316 KB Output is correct
50 Correct 1511 ms 121656 KB Output is correct
51 Correct 1446 ms 121672 KB Output is correct
52 Correct 1461 ms 119228 KB Output is correct
53 Correct 1428 ms 118912 KB Output is correct
54 Correct 1418 ms 118892 KB Output is correct
55 Correct 1575 ms 120536 KB Output is correct