제출 #1140098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140098		SmuggingSpun	Triple Jump (JOI19_jumps)	C++20	100 / 100	1275 ms	201648 KiB

jumps

#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
const int lim = 5e5 + 5;
const int INF = 1e9;
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
int n, q, a[lim], log_v[lim], spt[lim][19];
int get_max(int l, int r){
	if(l > r){
		return -1;
	}
	int k = log_v[r - l + 1];
	return max(spt[l][k], spt[r - (1 << k) + 1][k]);
}
namespace sub1{
	void solve(){
		for(int _ = 0; _ < q; _++){
			int l, r, ans = 0;
			cin >> l >> r;
			for(int i = l; i < r; i++){
				for(int j = i + 1; j < r; j++){
					for(int k = r; k > j; k--){
						if(k - j < j - i){
							break;
						}
						maximize(ans, a[i] + a[j] + a[k]);
					}
				}
			}
			cout << ans << "\n";
		}
	}
}
namespace sub2{
	void solve(){
		vector<vector<int>>range_max(n + 1, vector<int>(n + 1)), dp(n + 1, vector<int>(n + 1));
		for(int i = 1; i <= n; i++){
			range_max[i][i] = a[i];
			for(int j = i + 1; j <= n; j++){
				range_max[i][j] = max(range_max[i][j - 1], a[j]);
			}
		}
		for(int i = n; i > 2; i--){
			dp[i - 2][i] = a[i] + a[i - 1] + a[i - 2];
		}
		for(int len = 3; len < n; len++){
			for(int r = n; r > len; r--){
				int l = r - len;
				dp[l][r] = max(max(dp[l][r - 1], dp[l + 1][r]), a[l] + a[r] + range_max[l + 1][l + (len >> 1)]);
			}
		}
		for(int _ = 0; _ < q; _++){
			int l, r;
			cin >> l >> r;
			cout << dp[l][r] << "\n";
		}
	}
}
namespace sub3{
	void solve(){
		log_v[0] = -1;
		for(int i = 1; i <= n; i++){
			log_v[i] = log_v[i >> 1] + 1;
			spt[i][0] = a[i];
		}
		for(int j = 1; j < 18; j++){
			for(int i = 1; i + (1 << j) - 1 <= n; i++){
				spt[i][j] = max(spt[i][j - 1], spt[i + (1 << (j - 1))][j - 1]);
			}
		}
		vector<int>right_max(n + 1);
		stack<int>st;
		for(int i = n; i > 0; st.push(i--)){
			while(!st.empty() && a[st.top()] < a[i]){
				st.pop();
			}
			right_max[i] = (st.empty() ? -1 : st.top());
		}
		int l, r, ans = 0;
		cin >> l >> r;
		vector<int>suf(n + 2, -INF);
		for(int i = r; i >= l; i--){
			suf[i] = max(suf[i + 1], a[i]);
		}
		for(int i = l; i < r; i++){
			int x = i + 1;
			while(true){
				int T = (x << 1) - i;
				if(T > r){
					break;
				}
				maximize(ans, a[i] + a[x] + suf[T]);
				if(get_max(i + 1, x - 1) >= a[i]){
					break;
				}
				if((x = right_max[x]) == -1){
					break;
				}
			}
		}
		cout << ans << "\n";
	}
}
namespace sub4{
	struct Data{
		int min_sum, max_sum, opt_sum;
		Data(){}
		Data(int _min_sum, int _max_sum, int _opt_sum) : min_sum(_min_sum), max_sum(_max_sum), opt_sum(_opt_sum) {}
	};
	Data st[lim << 2];
	Data merge(Data left, Data right){
		if(left.min_sum == -1){
			return right;
		}
		if(right.min_sum == -1){
			return left;
		}
		return Data(min(left.min_sum, right.min_sum), max(left.max_sum, right.max_sum), max(left.opt_sum, right.opt_sum));
	}
	void apply(int id, int l, int r, int x){
		st[id] = Data(x, x, x + get_max(l, r));
	}
	void push_down(int id, int l, int r, int m){
		if(st[id].min_sum == st[id].max_sum){
			apply(id << 1, l, m, st[id].min_sum);
			apply(id << 1 | 1, m + 1, r, st[id].min_sum);
		}
	}
	void update(int id, int l, int r, int u, int v, int x){
		if(l > v || r < u || st[id].min_sum >= x){
			return;
		}
		if(u <= l && v >= r && st[id].max_sum <= x){
			apply(id, l, r, x);
			return;
		} 
		int m = (l + r) >> 1;
		push_down(id, l, r, m);
		update(id << 1, l, m, u, v, x);
		update(id << 1 | 1, m + 1, r, u, v, x);
		st[id] = merge(st[id << 1], st[id << 1 | 1]);
	}
	Data get(int id, int l, int r, int u, int v){
		if(l > v || r < u){
			return Data(-1, 0, 0);
		}
		if(u <= l && v >= r){
			return st[id];
		}
		int m = (l + r) >> 1;
		push_down(id, l, r, m);
		return merge(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
	}
	void solve(){
		log_v[0] = -1;
		for(int i = 1; i <= n; i++){
			log_v[i] = log_v[i >> 1] + 1;
			spt[i][0] = a[i];
		}
		for(int j = 1; j < 19; j++){
			for(int i = 1; i + (1 << j) - 1 <= n; i++){
				spt[i][j] = max(spt[i][j - 1], spt[i + (1 << (j - 1))][j - 1]);
			}
		}
		vector<int>right_max(n + 1);
		stack<int>st;
		for(int i = n; i > 0; st.push(i--)){
			while(!st.empty() && a[st.top()] < a[i]){
				st.pop();
			}
			right_max[i] = (st.empty() ? -1 : st.top());
		}
		vector<vector<int>>range(n + 1);
		vector<vector<pair<int, int>>>query(n + 1);
		for(int i = 1; i < n; i++){
			int x = i + 1;
			while(true){
				int T = (x << 1) - i;
				if(T > n){
					break;
				}
				range[i].emplace_back(x);
				if(get_max(i + 1, x - 1) >= a[i]){
					break;
				}
				if((x = right_max[x]) == -1){
					break;
				}
			}
		}
		vector<int>ans(q);
		for(int i = 0; i < q; i++){
			int l, r;
			cin >> l >> r;
			query[l].emplace_back(r, i);
		}
		for(int l = n; l > 0; l--){
			for(int& r : range[l]){
				update(1, 1, n, (r << 1) - l, n, a[l] + a[r]);
			}
			for(auto& [r, i] : query[l]){
				ans[i] = get(1, 1, n, l, r).opt_sum;
			}
		}
		for(int& x : ans){
			cout << x << "\n";
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	cin >> q;
	if(n <= 100 && q <= 100){
		sub1::solve();
	}
	else if(n <= 5000){
		sub2::solve();
	}
	else if(n <= 200000 && q == 1){
		sub3::solve();
	}
	else{
		sub4::solve();
	}
}

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In function 'int main()':
jumps.cpp:217:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  217 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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