제출 #320381

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
320381		hhhhaura	3단 점프 (JOI19_jumps)	C++14	100 / 100	1199 ms	90912 KiB

jumps

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define print(x) cout << #x <<" = " << x << endl
#define pprint(x) cout << #x <<" = (" << x.first <<" , " << x.second <<")\n"
#define ceil(a, b) ((a + b - 1) / b)
#define all(x) x.begin(), x.end()

#define INF 1000000000000000000
#define MAXN 1000005
#define MOD 1000000007
#define eps (1e-9)

#define int long long int 
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#define get(L, R) ((L + R) | (L != R))
using namespace std;
struct node {
	int A , B, C;
};
struct query {
	int L, R, id;
	bool operator<(query b) {
		return L > b.L;
	}
};
int n, q;
vector<query> qry;
vector<int> a, ans; 
vector<vector<int>> ps;
vector<node> seg;
void build() {
	stack<int> st;
	rep(i, 1, n) {
		while(st.size() && a[st.top()] <= a[i]) {
			ps[st.top()].push_back(i), st.pop();
		}
		if(st.size()) ps[st.top()].push_back(i);
		st.push(i);
	}
//	rep(i, 1, n) {
//		print(i), puts("");
//		for(auto j : ps[i]) print(j);
//		puts("\n\n");
//	}
	return;
}
void pull(int L, int R) {
	int mid = (L + R) / 2, nd = get(L, R);
	seg[nd].A = max(seg[get(L, mid)].A, seg[get(mid + 1,R)].A);
	seg[nd].C = max({seg[get(L, mid)].C, seg[get(mid + 1,R)].C, seg[nd].A + seg[nd].B });
	return;
}
void build1(int L, int R) {
	if(L == R) seg[get(L, R)].A = seg[get(L,R)].C = a[L] ;
	else {
		int mid = (L + R) / 2;
		build1(L, mid), build1(mid + 1, R);
		pull(L, R); 
	}
	return;
}
void modify(int L, int R, int l, int r, int val) {
//	pprint(pii(L,R)), print(val);
	if(l > R || r < L) return;
	if(l <= L && r >= R) {
//		print(val);
		seg[get(L, R)].B = max(seg[get(L, R)].B, val);
		seg[get(L, R)].C = max(seg[get(L,R)].C, seg[get(L, R)].B + seg[get(L,R)].A);
//		print(seg[get(L,R)].C);
	}
	else {
		int mid = (L + R) / 2;
		modify(L, mid, l, r, val), modify(mid + 1, R, l, r, val);
		pull(L,R);
	}
	return;
}
pii query(int L, int R, int l, int r) {
	if(l > R || r < L) return {0, 0};
//	pprint(pii(L,R));
	if(l <= L && r >= R) {
//		 pprint(pii(seg[get(L,R)].A, seg[get(L,R)].C));
		 return pii(seg[get(L,R)].A, seg[get(L,R)].C);
	} 
	else {
		int mid = (L + R) / 2;
		pii a = query(L, mid, l, r), b = query(mid + 1, R, l, r);
		int ans = max(max(a.first, b.first) + seg[get(L,R)].B, max(a.second, b.second));
		pii rr = pii(max(a.first, b.first), ans);
//		pprint(pii(L,R)), pprint(rr);
		return rr;
	}
}
void proc(int id) {
	for(int i : ps[id]) {
		int rr = 2 * i - id;
		if(rr > n) continue;
		modify(1, n, rr, n, a[i] + a[id]);
	}
	return;
}
void solve() {
	build(), build1(1, n), sort(all(qry));
	int cur = n;
	for(auto i : qry) {
		while(cur >= i.L) proc(cur--);
//		pprint(pii(i.L, i.R));
		pii aa = query(1, n, i.L + 2, i.R);
		ans[i.id] = aa.second;
//		puts("\n\n");
	}
	return;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	
	cin >> n, seg.resize(2 * n + 2);
	a.assign(n + 1 ,0), ps.assign(n + 1, vector<int>(0));
	rep(i, 1, n) cin >> a[i];
	
	cin >> q, qry.resize(q), ans.resize(q);
	rep(i, 0, q-1) cin >> qry[i].L >> qry[i].R, qry[i].id = i;
	
	solve();
	rep(i, 0, q-1) cout << ans[i] <<"\n";
	return 0; 
} 

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

jumps.cpp:3: warning: ignoring #pragma loop  [-Wunknown-pragmas]
    3 | #pragma loop-opt(on)
      |

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