제출 #1267646

#제출 시각아이디문제언어결과실행 시간메모리
1267646ducdev3단 점프 (JOI19_jumps)C++20
100 / 100
728 ms143280 KiB
// Author: 4uckd3v - Nguyen Cao Duc #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; const int MAX_N = 5e5; const int MOD = 1e9 + 7; template <class X, class Y> bool maximize(X &x, const Y &y) { if (x >= y) return false; x = y; return true; }; int n, q; int a[MAX_N + 5]; vector<ii> queries; namespace SUBTASK_12 { const int N = 5000; int mx[N + 5][N + 5], ans[N + 5][N + 5]; void Solve() { for (int i = 1; i <= n; i++) { mx[i][i] = a[i]; for (int j = i + 1; j <= n; j++) { mx[i][j] = max(mx[i][j - 1], a[j]); }; }; for (int l = 1; l <= n; l++) { for (int r = l + 2; r <= n; r++) { ans[l][r] = a[l] + a[r] + mx[l + 1][(l + r) >> 1]; }; }; for (int len = 3; len <= n; len++) { for (int l = 1; l + len - 1 <= n; l++) { int r = l + len - 1; maximize(ans[l][r], ans[l + 1][r]); maximize(ans[l][r], ans[l][r - 1]); maximize(ans[l][r], ans[l + 1][r - 1]); }; }; for (ii q : queries) { int l = q.first, r = q.second; cout << ans[l][r] << "\n"; }; }; }; // namespace SUBTASK_12 namespace SUBTASK_34 { const int N = MAX_N; const int Q = 5e5; int ans[Q + 5], seg[4 * N + 5], mx[4 * N + 5], lazy[4 * N + 5]; vector<ii> qu[Q + 5]; vector<int> cand[N + 5]; void build(int node, int l, int r) { if (l == r) return mx[node] = a[l], void(); int mid = (l + r) >> 1; build(node << 1, l, mid); build(node << 1 | 1, mid + 1, r); mx[node] = max(mx[node << 1], mx[node << 1 | 1]); }; void down(int node) { if (lazy[node] == 0) return; for (int i = 0; i < 2; i++) { maximize(seg[node << 1 | i], mx[node << 1 | i] + lazy[node]); maximize(lazy[node << 1 | i], lazy[node]); }; lazy[node] = 0; }; void update(int node, int l, int r, int u, int v, int val) { if (l > v || r < u) return; if (l >= u && r <= v) { maximize(seg[node], mx[node] + val); maximize(lazy[node], val); return; }; down(node); int mid = (l + r) >> 1; update(node << 1, l, mid, u, v, val); update(node << 1 | 1, mid + 1, r, u, v, val); seg[node] = max(seg[node << 1], seg[node << 1 | 1]); }; void update(int l, int r, int val) { update(1, 1, n, l, r, val); }; int get(int node, int l, int r, int u, int v) { if (l > v || r < u) return -1e9; if (l >= u && r <= v) return seg[node]; down(node); int mid = (l + r) >> 1; return max(get(node << 1, l, mid, u, v), get(node << 1 | 1, mid + 1, r, u, v)); }; int get(int l, int r) { return get(1, 1, n, l, r); }; void Solve() { stack<int> st; for (int i = 1; i <= n; i++) { while (!st.empty() && a[st.top()] < a[i]) { cand[st.top()].push_back(i); st.pop(); }; if (!st.empty()) cand[st.top()].push_back(i); st.push(i); }; for (int i = 0; i < q; i++) { int l = queries[i].first, r = queries[i].second; qu[l].push_back(make_pair(r, i)); }; build(1, 1, n); for (int i = n; i >= 1; i--) { for (int j : cand[i]) if (2 * j - i <= n) update(2 * j - i, n, a[i] + a[j]); for (ii q : qu[i]) ans[q.second] = get(i + 2, q.first); }; for (int i = 0; i < q; i++) cout << ans[i] << '\n'; }; }; // namespace SUBTASK_34 int main() { ios_base::sync_with_stdio(0); cin.tie(0); if (fopen("MAIN.INP", "r")) { freopen("MAIN.INP", "r", stdin); freopen("MAIN.OUT", "w", stdout); }; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; }; cin >> q; queries.resize(q); for (ii &query : queries) cin >> query.first >> query.second; if (n <= 5000) return SUBTASK_12::Solve(), 0; SUBTASK_34::Solve(); };

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

jumps.cpp: In function 'int main()':
jumps.cpp:155:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         freopen("MAIN.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:156:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |         freopen("MAIN.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...