# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
138113 | 2019-07-29T11:27:40 Z | sebinkim | 3단 점프 (JOI19_jumps) | C++14 | 122 ms | 45816 KB |
#include <bits/stdc++.h> using namespace std; typedef pair <int, int> pii; struct node{ int lv, rv, mv; node() : lv(-1e9), rv(-1e9), mv(-1e9) {} node(int lv, int rv) : lv(lv), rv(rv), mv(-1e9) {} node operator + (node &n) { node ret; ret.lv = max(lv, n.lv); ret.rv = max(rv, n.rv); ret.mv = max(max(mv, n.mv), lv + n.rv); return ret; } }; struct segtree{ node T[1101010]; int sz = 1 << 19; void init(int n, int *X) { int i; for(i=1; i<=n; i++){ T[sz + i] = node(-1e9, X[i]); } for(i=sz-1; i; i--){ T[i] = T[i << 1] + T[i << 1 | 1]; } } void update(int p, int v) { p += sz; if(T[p].lv >= v) return; T[p] = node(v, T[p].rv); for(p>>=1; p; p>>=1){ T[p] = T[p << 1] + T[p << 1 | 1]; } } int getval(int l, int r) { node lv, rv; l += sz; r += sz; for(; l<=r; ){ if(l & 1) lv = lv + T[l]; if(~r & 1) rv = T[r] + rv; l = l + 1 >> 1; r = r - 1 >> 1; } return (lv + rv).mv; } }; segtree T; vector <pii> V[505050], Q[505050]; vector <int> S; int X[505050], A[505050]; int n; int main() { int q, i, j, t, l, r; scanf("%d", &n); for(i=1; i<=n; i++){ scanf("%d", X + i); for(; !S.empty(); S.pop_back()){ j = S.back(); t = i + i - j - 1; if(t <= n) V[j].emplace_back(t, X[j] + X[i]); if(X[t] > X[i]) break; } S.push_back(i); } T.init(n, X); scanf("%d", &q); for(i=1; i<=q; i++){ scanf("%d%d", &l, &r); Q[l].emplace_back(r, i); } for(i=n; i>=1; i--){ for(pii &t: V[i]){ T.update(t.first, t.second); } for(pii &q: Q[i]){ A[q.second] = T.getval(i, q.first); } } for(i=1; i<=q; i++){ printf("%d\n", A[i]); } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 38 ms | 36984 KB | Output is correct |
2 | Incorrect | 38 ms | 36984 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 38 ms | 36984 KB | Output is correct |
2 | Incorrect | 38 ms | 36984 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 122 ms | 45816 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 38 ms | 36984 KB | Output is correct |
2 | Incorrect | 38 ms | 36984 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |