Submission #202485

#	Time	Username	Problem	Language	Result	Execution time	Memory
202485		onjo0127	Triple Jump (JOI19_jumps)	C++11	100 / 100	1432 ms	89960 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

struct node { int v, f, a; } T[1050000];
const node EMP = {0, 0, 0};
node operator +(node L, node R) {
	node ret;
	ret.f = max(L.f, R.f);
	ret.a = max(L.a, R.a);
	ret.v = max({L.v, R.v, L.f + R.a});
	return ret;
}

int A[500009], ans[500009], F[500009];
vector<pii> query[500009];
vector<int> add[500009];

void init(int idx, int s, int e) {
	if(s == e) {
		T[idx] = {A[s], 0, A[s]};
		return;
	}
	int m = s+e >> 1;
	init(idx*2, s, m);
	init(idx*2+1, m+1, e);
	T[idx] = T[idx*2] + T[idx*2+1];
}

void upd(int idx, int s, int e, int p, int v) {
	if(p < s || e < p) return;
	if(s == e) {
		T[idx].f = v;
		T[idx].v = T[idx].f + T[idx].a;
		return;
	}
	int m = s+e >> 1;
	upd(idx*2, s, m, p, v);
	upd(idx*2+1, m+1, e, p, v);
	T[idx] = T[idx*2] + T[idx*2+1];
}

node get(int idx, int s, int e, int l, int r) {
	if(r < s || e < l) return EMP;
	if(l <= s && e <= r) return T[idx];
	int m = s+e >> 1;
	return get(idx*2, s, m, l, r) + get(idx*2+1, m+1, e, l, r);
}

int main() {
	int N; scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d", &A[i]);
	int Q; scanf("%d", &Q);
	for(int i=0; i<Q; i++) {
		int l, r; scanf("%d%d",&l,&r);
		query[l].push_back({r, i});
	}
	vector<int> S;
	for(int i=1; i<=N; i++) {
		while(S.size() && A[S.back()] < A[i]) {
			add[S.back()].push_back(i);
			S.pop_back();
		}
		if(S.size()) add[S.back()].push_back(i);
		S.push_back(i);
	}
	init(1, 1, N);
	for(int i=N; i>=1; i--) {
		for(auto& it: add[i]) if(2*it - i <= N) {
			F[2*it - i] = max(F[2*it - i], A[i] + A[it]);
			upd(1, 1, N, 2*it - i, F[2*it - i]);
		}
		for(auto& it: query[i]) ans[it.second] = get(1, 1, N, i, it.first).v;
	}
	for(int i=0; i<Q; i++) printf("%d\n", ans[i]);
	return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'void init(int, int, int)':
jumps.cpp:24:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s+e >> 1;
          ~^~
jumps.cpp: In function 'void upd(int, int, int, int, int)':
jumps.cpp:37:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s+e >> 1;
          ~^~
jumps.cpp: In function 'node get(int, int, int, int, int)':
jumps.cpp:46:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s+e >> 1;
          ~^~
jumps.cpp: In function 'int main()':
jumps.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N; scanf("%d", &N);
         ~~~~~^~~~~~~~~~
jumps.cpp:52:31: 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", &A[i]);
                          ~~~~~^~~~~~~~~~~~~
jumps.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int Q; scanf("%d", &Q);
         ~~~~~^~~~~~~~~~
jumps.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int l, r; scanf("%d%d",&l,&r);
             ~~~~~^~~~~~~~~~~~~~

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