Submission #634756

#	Time	Username	Problem	Language	Result	Execution time	Memory
634756		rainliofficial	Triple Jump (JOI19_jumps)	C++17	100 / 100	1049 ms	61784 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 Node{
    int ab, c, abc;
};

struct segtree{
    const int PO2 = 131072; // least power of 2 greater than MAXN; 
    int n;
    Node identity = {-INF, -INF, -INF};
    vector<Node> 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
    }
    ll query(int a, int b){
        if (a > b){
            return -INF;
        }
        return query(0, 0, n-1, a, b).abc;
    }
    Node query(int node, int l, int r, int a, int b) { // inclusive 0-indexed
		if (a <= l && r <= b) {
			return seg[node];
		}
		Node 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, bool updC) { // inclusive 0-indexed
    if (a >= n){
        return;
    }
		update(0, 0, n-1, a, x, updC);
	}
    void update(int node, int l, int r, int a, int x, bool updC) {
		if (l == r) { 
            if (updC){
                ckmax(seg[node].c, x);
            }else{
                ckmax(seg[node].ab, x);
            }
			seg[node].abc = seg[node].ab + seg[node].c;
			return;
		}
		int mid = (l + r) / 2;
		if (a <= mid) {
			update(node * 2 + 1, l, mid, a, x, updC);
		}else{
			update(node * 2 + 2, mid + 1, r, a, x, updC);
		}
		seg[node] = combine(seg[node * 2 + 1], seg[node * 2 + 2]);
	}
    Node combine(Node a, Node b){
        return {max(a.ab, b.ab), max(a.c, b.c), max({a.abc, b.abc, a.ab + b.c})};
    }
};

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);
    sort(ab.begin(), ab.end(), greater<pii>());
    int pt = 0;
    vector<array<int, 3>> queries;
    cin >> q;
    for (int i=0; i<q; i++){
        int l, r;
        cin >> l >> r;
        l--; r--;
        queries.push_back({l, r, i});
    }
    sort(queries.begin(), queries.end(), [](const array<int, 3> a1, const array<int, 3> a2){
        return make_pair(a1[0], a1[1]) > make_pair(a2[0], a2[1]);
    });
    for (int i=0; i<n; i++){
        seg.update(i, arr[i], true);
    }
    vector<int> ans(q);
    for (int i=0; i<q; i++){
        while (pt < sz(ab) && ab[pt].first >= queries[i][0]){
            seg.update(ab[pt].second + (ab[pt].second - ab[pt].first), arr[ab[pt].first] + arr[ab[pt].second], false);
            pt++;
        }
        ans[queries[i][2]] = seg.query(queries[i][0], queries[i][1]);
    }
    for (int i : ans){
        cout << i << "\n";
    }
}

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

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