Submission #1194065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194065		Bui_Quoc_Cuong	3단 점프 (JOI19_jumps)	C++20	100 / 100	735 ms	79056 KiB

jumps

//#pragma GCC optimize("O2")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;

int n, q;
int a[N];
int Lq[N], Rq[N];

namespace sub1{
	int ma[N];

	void solve(){
		for(int _ = 1; _ <= q; _++) {
			// int L, R; cin >> L >> R;
			int L = Lq[_], R = Rq[_];

			long long ans = 0;	

			for(int i = L; i <= R; i++){
				for(int j = L; j <= i - 1; j++){
					ma[i - j] = a[j] + a[i];
				}

				for(int len = 0; len <= R - L + 1; len++){
					ma[len] = max(ma[len], ma[len - 1]);
				}

				for(int j = i + 1; j <= R; j++){
					ans = max(ans, a[j] + 1LL * ma[j - i]);
				}
			}	

			cout << ans << "\n";

			for(int len = 0; len <= R - L + 1; len++){
				ma[len] = - 2e9;
			}
		}		
	}
}

namespace sub2{	
	long long lazy[4 * N], st[4 * N], mx[4 * N];

	void down(int id){
		if(lazy[id] == 0) return;

		st[id << 1] = max(st[id << 1], mx[id << 1] + lazy[id]);
		st[id << 1 | 1] = max(st[id << 1 | 1], mx[id << 1 | 1] + lazy[id]);

		lazy[id << 1] = max(lazy[id << 1], lazy[id]);
		lazy[id << 1 | 1] = max(lazy[id << 1 | 1], lazy[id]);

		lazy[id] = 0;
	}

	void build(int id, int l, int r){
		if(l == r){
			mx[id] = a[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(id << 1, l, mid);
		build(id << 1 | 1, mid + 1, r);
		mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
	}

	void update(int id, int l, int r, int u, int v, long long val){
		if(l > v || r < u) return;
		if(l >= u && r <= v){
			st[id] = max(st[id], mx[id] + val);
			lazy[id] = max(lazy[id], val);
			return;
		}
		down(id);
		int mid = (l + r) >> 1;
		update(id << 1, l, mid, u, v, val);
		update(id << 1 | 1, mid + 1, r, u, v, val);
		st[id] = max(st[id << 1], st[id << 1 | 1]);
	}

	long long get(int id, int l, int r, int u, int v){
		if(l > v || r < u) return 0;
		if(l >= u && r <= v) return st[id];
		down(id);
		int mid = (l + r) >> 1;
		return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
	}

	long long ans[N];
	vector <pair <int, int>> qry[N];

	void solve(){
		build(1, 1, n);
		for(int i = 1; i <= q; i++){
			qry[Lq[i]].push_back(make_pair(Rq[i], i));
		}

		stack <int> st;
		for(int i = n; i >= 1; i--){
			while(!st.empty() && a[i] >= a[st.top()]){
				update(1, 1, n, max(1, 2 * st.top() - i), n, a[i] + a[st.top()]);
				st.pop();
			}
			if(st.size()) update(1, 1, n, max(1, 2 * st.top() - i), n, a[i] + a[st.top()]);
			st.push(i);

			for(auto x : qry[i]){
				ans[x.second] = max(ans[x.second], get(1, 1 , n, i, x.first));
			}
		}

		for(int i = 1; i <= q; i++){
			cout << ans[i] << "\n";
		}
	}
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define KO ""
    if(fopen(KO".inp", "r")){
        freopen(KO".inp", "r", stdin); freopen(KO".out", "w", stdout);
    }	

    cin >> n;
    for(int i = 1; i <= n; i++){
    	cin >> a[i];
    }
    cin >> q;
    for(int i = 1; i <= q; i++){
    	cin >> Lq[i] >> Rq[i];
    }

    // return sub1 :: solve(), 0;
    return sub2 :: solve(), 0;

    return void(cerr << "\nKO : " << 0.001 * clock() << "s "), 0;
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(KO".inp", "r", stdin); freopen(KO".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:125:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(KO".inp", "r", stdin); freopen(KO".out", "w", stdout);
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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