Submission #1010634

#TimeUsernameProblemLanguageResultExecution timeMemory
1010634danikoynovTriple Jump (JOI19_jumps)C++14
0 / 100
1 ms604 KiB
#include<bits/stdc++.h> #define endl '\n' const int MAX_N = 110; int n, q, a[MAX_N]; void input() { std::cin >> n; for (int i = 1; i <= n; i ++) std::cin >> a[i]; } std::vector < std::pair < int, int > > fun; void precompute_pairs() { std::stack < int > st; for (int i = n; i > 0; i --) { while(!st.empty() && a[st.top()] >= a[i]) { fun.push_back({i, st.top()}); st.pop(); } st.push(i); } while(!st.empty()) st.pop(); for (int i = n; i > 0; i --) { while(!st.empty() && a[st.top()] <= a[i]) { fun.push_back({i, st.top()}); st.pop(); } st.push(i); } } int fp[MAX_N]; void single_query(int l, int r) { fp[r + 1] = 0; for (int i = r; i >= l; i --) { fp[i] = std::max(fp[i + 1], a[i]); } int res = 0; for (std::pair < int, int > cur : fun) { int id = 2 * cur.second - cur.first; if (id > r || cur.first < l) continue; ///std::cout << "query " << l << " " << r << " " << cur.first << " " << cur.second << endl; res = std::max(res, a[cur.first] + a[cur.second] + fp[id]); } std::cout << res << endl; } void answer_queries() { std::cin >> q; for (int i = 1; i <= q; i ++) { int l, r; std::cin >> l >> r; single_query(l, r); } } void solve() { input(); precompute_pairs(); answer_queries(); } void speed() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); } int main() { speed(); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...