제출 #227326

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

jumps

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct st_node {
	ll mxv, mx;
	ll lz;
};

const int MAXN = 5e5+5;
const ll INF = 1e18;
int input[MAXN];
vector<tuple<int, int, int> > qv; //{r, l, id}
vector<tuple<int, int, int> > jumps; //{r, l, val}
st_node seg[MAXN*4];
ll ans[MAXN];
int n, q;

void st_process() {
	stack<int> st;
	input[0] = 2e9;
	st.push(0);
	for(int i = 1; i <= n; i++) {
		while(input[st.top()] < input[i]) st.pop();
		if(st.top() != 0) {
			int id = st.top();
			jumps.push_back({ i+i-id, id, input[i]+input[id] });
		}
		st.push(i);
	}
	while(st.size()) st.pop();
	input[n+1] = 2e9;
	st.push(n+1);
	for(int i = n; i >= 1; i--) {
		while(input[st.top()] < input[i]) st.pop();
		if(st.top() != n+1) {
			int id = st.top();
			jumps.push_back({ id+id-i, i, input[i]+input[id] });
		}
		st.push(i);
	}
	sort(jumps.begin(), jumps.end());
}

void refresh(int u, int l, int r) {
	ll val = seg[u].lz;
	seg[u].lz = 0;
	seg[u].mx = max(seg[u].mx, seg[u].mxv+val);
	if(l == r) return;
	int vl = u*2;
	int vr = vl|1;
	seg[vl].lz = max(seg[vl].lz, val);
	seg[vr].lz = max(seg[vr].lz, val);
}

ll query(int u, int l, int r, int ql, int qr) {
	refresh(u, l, r);
	if(ql > r || qr < l) return -INF;
	if(ql <= l && qr >= r) return seg[u].mx;
	int m = (l+r)/2;
	int vl = u*2;
	int vr = vl|1;
	return max( query(vl, l, m, ql, qr), query(vr, m+1, r, ql, qr) );
}

void build(int u, int l, int r) {
	seg[u].mx = seg[u].mxv = -INF;
	if(l == r) return;
	int m = (l+r)/2;
	int vl = u*2;
	int vr = vl|1;
	build(vl, l, m);
	build(vr, m+1, r);
}

void activate(int u, int l, int r, int qi, ll val) {
	refresh(u, l, r);
	if(qi < l || qi > r) return;
	if(l == r) {
		seg[u].mxv = max(seg[u].mxv, val);
		seg[u].mx = max(seg[u].mx, val);
		return;
	}
	int m = (l+r)/2;
	int vl = u*2;
	int vr = vl|1;
	activate(vl, l, m, qi, val);
	activate(vr, m+1, r, qi, val);
	seg[u].mx = max(seg[vl].mx, seg[vr].mx); 
	seg[u].mxv = max(seg[vl].mxv, seg[vr].mxv); 
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &input[i]);
	scanf("%d", &q);
	for(int i = 1; i <= q; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		qv.push_back({b, a, i});
	}
	sort(qv.begin(), qv.end());

	st_process();
	// for(auto jump : jumps) printf("%d %d %d\n", get<0>(jump), get<1>(jump), get<2>(jump));

	build(1, 1, n);

	int pj = 0, pq = 0;
	for(int i = 1; i <= n; i++) {
		while(pj < jumps.size() && get<0>(jumps[pj]) <= i) {
			int l, r, val;
			tie(r, l, val) = jumps[pj];
			// printf("activate %d %d\n", l, val);
			activate(1, 1, n, l, val);
			pj++;
		}

		refresh(1, 1, n);
		seg[1].lz = input[i];
		refresh(1, 1, n);
		// printf("upd %d\n", input[i]);
		// printf("ans %d...\n", i);
		while(pq < qv.size() && get<0>(qv[pq]) <= i) {
			int l, r, id;
			tie(r, l, id) = qv[pq];
			ans[id] = query(1, 1, n, l, r);
			pq++;
		}
	}

	for(int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
}

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

jumps.cpp: In function 'int main()':
jumps.cpp:111:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(pj < jumps.size() && get<0>(jumps[pj]) <= i) {
         ~~~^~~~~~~~~~~~~~
jumps.cpp:124:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(pq < qv.size() && get<0>(qv[pq]) <= i) {
         ~~~^~~~~~~~~~~
jumps.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
jumps.cpp:95:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= n; i++) scanf("%d", &input[i]);
                              ~~~~~^~~~~~~~~~~~~~~~~
jumps.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
jumps.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~

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