oj.uz

답안 #634742

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
634742 2022-08-24T19:35:13 Z rainliofficial 3단 점프 (JOI19_jumps) C++17
32 / 100
 4000 ms 13064 KB 
#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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Execution timed out 4069 ms 1496 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 12972 KB Output is correct
2 Correct 48 ms 12988 KB Output is correct
3 Correct 46 ms 13056 KB Output is correct
4 Correct 69 ms 13064 KB Output is correct
5 Correct 69 ms 12992 KB Output is correct
6 Correct 61 ms 12336 KB Output is correct
7 Correct 62 ms 12224 KB Output is correct
8 Correct 68 ms 12268 KB Output is correct
9 Correct 66 ms 12520 KB Output is correct

Subtask #4
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Execution timed out 4069 ms 1496 KB Time limit exceeded
12 Halted 0 ms 0 KB -