Submission #634742

#	Time	Username	Problem	Language	Result	Execution time	Memory
634742		rainliofficial	Triple Jump (JOI19_jumps)	C++17	32 / 100	4069 ms	13064 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
#define sz(x) (int)x.size()

/* 
Date: 2022/08/24 15:14
Problem Link: https://oj.uz/problem/view/JOI19_jumps
Topic(s):
Time Spent:
Solution Notes:
Consider pairs of possible (a, b), and let them be at indices (i, j). We observe that in range [i, j], a and b must
be the two largest element, and everything in between is smaller. 
Therefore, we can fix whichever one of a or b that's smaller, and then find the other endpoint in O(N) time in total
by using a monotone stack. 
One we have all (a, b), it is a matter of determining c. We can naively use a segment tree to query every c (subtask 2),
or use a suffix max (subtask 3). 
To get the full solution, let's store the value of a + b at the least location of c that it corresponds to. Each node in 
segment tree would essientially store the following values:
1. max a+b
2. max c
3. max a+b+c 
*/

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x);
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(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

const int MAXN = 2e5+5, INF = 1e9;
int n, q;

struct segtree{
    const int PO2 = 131072; // least power of 2 greater than MAXN; 
    int n, identity = 0;
    vector<ll> seg;
    vector<int> arr;
    void init(int n){
        this->n = n;
        seg.resize(4*n, identity); // change to 4*N if we want to reinitialize the segtree multiple times on difference values of N
    }
    void build(vector<int>& arr){
        this->arr = arr;
        build(0, 0, n-1);
    }
    void build(int node, int l, int r){
        if (l == r) {
			seg[node] = arr[l];
			return;
		}
		int mid = (l + r) / 2;
		build(node * 2 + 1, l, mid);
		build(node * 2 + 2, mid + 1, r);
		// change this
		seg[node] = combine(seg[node * 2 + 1], seg[node * 2 + 2]);
    }
    ll query(int a, int b){
        if (a > b){
            return -INF;
        }
        return query(0, 0, n-1, a, b);
    }
    ll query(int node, int l, int r, int a, int b) { // inclusive 0-indexed
		if (a <= l && r <= b) {
			return seg[node];
		}
		ll ans = identity;
		int mid = (l + r) / 2;
		if (a <= mid) {
			ans = combine(ans, query(node * 2 + 1, l, mid, a, b));
		}
        if (b > mid){
			ans = combine(ans, query(node * 2 + 2, mid + 1, r, a, b));
		}
		return ans;
	}
    void update(int a, int x) { // inclusive 0-indexed
		update(0, 0, n-1, a, x);
	}
    void update(int node, int l, int r, int a, int x) {
		if (l == r) { 
			seg[node] = x;
			return;
		}
		int mid = (l + r) / 2;
		if (a <= mid) {
			update(node * 2 + 1, l, mid, a, x);
		}else{
			update(node * 2 + 2, mid + 1, r, a, x);
		}
		seg[node] = combine(seg[node * 2 + 1], seg[node * 2 + 2]);
	}
    ll combine(ll a, ll b){
        return max(a, b);
    }
};

int main(){
    cin.tie(0); ios_base::sync_with_stdio(0);
    // freopen("file.in", "r", stdin);
    // freopen("file.out", "w", stdout);
    cin >> n;
    vector<int> arr(n);
    for (int i=0; i<n; i++){
        cin >> arr[i];
    }
    // use monotonic stack to process the possible (a, b). 
    // assume a > b
    vector<pii> ab;
    stack<pii> st;
    for (int i=n-1; i>=0; i--){
        while (!st.empty() && st.top().first < arr[i]){
            st.pop();
        }
        if (!st.empty()){
            ab.push_back({i, st.top().second});
        }
        st.push({arr[i], i});
    }
    stack<pii> st2;
    swap(st2, st);
    for (int i=0; i<n; i++){
        while (!st.empty() && st.top().first < arr[i]){
            st.pop();
        }
        if (!st.empty()){
            ab.push_back({st.top().second, i});
        }
        st.push({arr[i], i});
    }
    dbg(ab)
    segtree seg;
    seg.init(n);
    seg.build(arr);
    cin >> q;
    for (int i=0; i<q; i++){
        int l, r;
        cin >> l >> r;
        l--; r--;
        ll ans = 0;
        for (pii x : ab){
            if (x.first >= l && x.second <= r){
                int d = x.second - x.first;
                ckmax(ans, arr[x.first] + arr[x.second] + seg.query(x.second + d, r));
            }
        }
        cout << ans << "\n";
    }
}

/**
 * Debugging checklist:
 * - Reset everything after each TC
 * - Integer overflow, index overflow
 * - Special cases?
 */

• Subtask 1: 5 / 5
• Subtask 2: 0 / 14
• Subtask 3: 27 / 27
• Subtask 4: 0 / 54