Submission #1310315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310315		nanaseyuzuki	Triple Jump (JOI19_jumps)	C++20	100 / 100	685 ms	76880 KiB

jumps

#include <bits/stdc++.h>
// Kazusa_Megumi
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;

#ifdef LOCAL
#include "C:\Users\Dell\Downloads\template\template\icpc-notebook\Utilities\debug.h"
#else
#define debug(...) 42
#endif

const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e9;

int n, q, a[mn], val[mn << 2], st[mn << 2], lz[mn << 2], ans[mn];

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

void down(int id, int l, int r){
	if(!lz[id] || l == r) return;
	lz[id << 1] = max(lz[id], lz[id << 1]);
	st[id << 1] = max(st[id << 1], val[id << 1] + lz[id]);
	lz[id << 1 | 1] = max(lz[id], lz[id << 1 | 1]);
	st[id << 1 | 1] = max(st[id << 1 | 1], val[id << 1 | 1] + lz[id]);

	lz[id] = 0;
}

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

int 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, l, r);
	int mid = (l + r) >> 1;
	return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v)); 
}

vector <pii> query[mn];
vector <int> line[mn];
/*
	Nhận xét 1: Cho các bộ ba (i, j, a), chỉ xét các cặp (i, j) sao cho max[i + 1 -> j - 1] < min(a[i], a[j])
	Chứng minh:
		Nếu tồn tại k mà (i < k < j) sao cho (i, k) hoặc (j, k) tốt hơn (i, j) thì sai do
		*) Vấn đề về khoảng cách j - i <= a - j, do thay k vào i hoặc j thì khoảng cách từ a tăng còn bên kia giảm
		=> luôn thỏa mãn
		*) Vấn đề về giá trị, do a[k] < min(a[j], a[i])
		=> ko thỏa mãn 
		=> dpcm
	
	Nhận xét 2: Số cặp (i, j) cần xét như trên chỉ có tối đa là O(2 * n) cặp
	Chứng minh: dùng stack cơ bản
*/
void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
	cin >> q;
	
	for(int i = 1; i <= q; i++){
		int l, r; cin >> l >> r;
		query[l].push_back({r, i});
	}
	stack <int> s;
	for(int i = 1; i <= n; i++){
		while(s.size() && a[s.top()] <= a[i]){
			line[s.top()].push_back(i);
			s.pop();
		}
		if(s.size()) line[s.top()].push_back(i);
		s.push(i);
	}

	for(int i = n; i >= 1; i--){
		for(auto j : line[i]){
			if(2 * j - i <= n){
				debug(j, i, 2 * j - i, a[i] + a[j]);
				update(1, 1, n, 2 * j - i, n, a[i] + a[j]);
			}
		}
		for(auto [r, id] : query[i]){
			debug(i, r, id, get(1, 1, n, i, r));
			ans[id] = get(1, 1, n, i, r);
		}
	}

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    if (fopen("Kazuki.INP", "r")) {
        freopen("Kazuki.INP", "r", stdin);
        freopen("Kazuki.OUT", "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

jumps.cpp:114:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  114 | main() {
      | ^~~~
jumps.cpp: In function 'int main()':
jumps.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen("Kazuki.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen("Kazuki.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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