Submission #1217066

#TimeUsernameProblemLanguageResultExecution timeMemory
1217066CodeLakVNTriple Jump (JOI19_jumps)C++20
100 / 100
626 ms49032 KiB
#include <bits/stdc++.h> using namespace std; #define task "main" #define no "NO" #define yes "YES" #define F first #define S second #define vec vector #define _mp make_pair #define ii pair<int, int> #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define evoid(val) return void(std::cout << val) #define FOR(i, a, b) for(int i = (a); i <= (b); ++i) #define FOD(i, b, a) for(int i = (b); i >= (a); --i) template<class X, class Y> bool maximize(X &x, Y y) { if (x < y) { x = y; return true; } return false; } const int MAX_N = (int)5e5 + 5; int n, q; int a[MAX_N]; vector<ii> query[MAX_N]; int ans[MAX_N]; struct IT { int lazy[4 * MAX_N], tree[4 * MAX_N], base[4 * MAX_N]; void build(int id, int l, int r) { if (l == r) { base[id] = a[l]; return; } int mid = (l + r) >> 1; build(2 * id, l, mid); build(2 * id + 1, mid + 1, r); base[id] = max(base[2 * id], base[2 * id + 1]); } void down(int id) { if (lazy[id] == 0) return; maximize(tree[2 * id], base[2 * id] + lazy[id]); maximize(tree[2 * id + 1], base[2 * id + 1] + lazy[id]); maximize(lazy[2 * id], lazy[id]); maximize(lazy[2 * id + 1], lazy[id]); lazy[id] = 0; } void update(int id, int l, int r, int u, int v, int val) { if (l > v || r < u) return; if (l >= u && r <= v) { maximize(tree[id], base[id] + val); maximize(lazy[id], val); return; } down(id); int mid = (l + r) >> 1; update(2 * id, l, mid, u, v, val); update(2 * id + 1, mid + 1, r, u, v, val); tree[id] = max(tree[2 * id], tree[2 * id + 1]); } int get(int id, int l, int r, int u, int v) { if (l > v || r < u) return 0; if (l >= u && r <= v) return tree[id]; down(id); int mid = (l + r) >> 1; return max(get(2 * id, l, mid, u, v), get(2 * id + 1, mid + 1, r, u, v)); } } segtree; void solve() { cin >> n; FOR(i, 1, n) cin >> a[i]; cin >> q; FOR(i, 1, q) { int l, r; cin >> l >> r; query[l].push_back({r, i}); } segtree.build(1, 1, n); stack<int> st; FOD(i, n, 1) { while (!st.empty() && a[st.top()] <= a[i]) { segtree.update(1, 1, n, max(1, 2 * st.top() - i), n, a[st.top()] + a[i]); st.pop(); } if (!st.empty()) segtree.update(1, 1, n, max(1, 2 * st.top() - i), n, a[st.top()] + a[i]); st.push(i); for (ii p : query[i]) ans[p.S] = segtree.get(1, 1, n, i,p.F); } FOR(i, 1, q) cout << ans[i] << "\n"; } int32_t main() { if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); bool multitest = 0; int numTest = 1; if (multitest) cin >> numTest; while (numTest--) { solve(); } return 0; } /* Lak lu theo dieu nhac!!!! */

Compilation message (stderr)

jumps.cpp: In function 'int32_t main()':
jumps.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...