Submission #711638

#	Time	Username	Problem	Language	Result	Execution time	Memory
711638		Thienu	Triple Jump (JOI19_jumps)	C++17	100 / 100	1865 ms	124444 KiB

jumps

#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 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54