이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 5e5 + 5;
int n, nq, a[N], t[4 * N], lazy[4 * N], mx[4 * N], f[4 * N], ans[N];
vector <int> opt[N];
vector <pair<int, ii> > q;
stack <int> st;
void build(int i, int l, int r) {
if(l == r) {
mx[i] = a[l];
return ;
}
int mid = l + r >> 1;
build(i << 1, l, mid);
build(i << 1 | 1, mid + 1, r);
mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
}
void down(int i) {
if(!down[i]) return ;
t[i << 1] = max(t[i << 1], lazy[i]);
f[i << 1] = max(f[i << 1], t[i << 1] + mx[i << 1]);
lazy[i << 1] = max(lazy[i << 1], lazy[i]);
t[i << 1 | 1] = max(t[i << 1 | 1], lazy[i]);
f[i << 1 | 1] = max(f[i << 1 | 1], t[i << 1 | 1] + mx[i << 1 | 1]);
lazy[i << 1 | 1] = max(lazy[i << 1 | 1], lazy[i]);
lazy[i] = 0;
}
void upd(int i, int l, int r, int u, int v, int val) {
if(l > v || u > r) return ;
if(u <= l && r <= v) {
t[i] = max(t[i], val);
lazy[i] = max(lazy[i], val);
f[i] = max(f[i], t[i] + mx[i]);
return ;
}
down(i);
int mid = l + r >> 1;
upd(i << 1, l, mid, u, v, val);
upd(i << 1 | 1, mid + 1, r, u, v, val);
f[i] = max(f[i << 1], f[i << 1 | 1]);
}
int get(int i, int l, int r, int u, int v) {
if(l > v || u > r) return 0;
if(u <= l && r <= v) return f[i];
down(i);
int mid = l + r >> 1;
return max(get(i << 1, l, mid, u, v) , get(i << 1 | 1, mid + 1, r, u, v));
}
main () {
cin.tie(0)->sync_with_stdio(0);
if(fopen("task.inp", "r")) {
freopen("task.inp", "r", stdin);
freopen("wa.out", "w", stdout);
}
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
for(int i = n; i >= 1; i--) {
while (!st.empty() && a[i] > a[st.top()]) {
opt[i].push_back(st.top());
st.pop();
}
if(!st.empty()) opt[i].push_back(st.top());
st.push(i);
}
cin >> nq;
for(int i = 1; i <= nq; i++) {
int l, r; cin >> l >> r;
q.push_back({i, {l, r}});
}
sort(q.begin(), q.end(), [] (pair<int, ii> x, pair<int, ii> y) {
return x.se.fi > y.se.fi;
});
int it = n;
for(int j = 0; j < nq; j++) {
int i = q[j].fi, l = q[j].se.fi, r = q[j].se.se;
while (it >= l) {
for(int b : opt[it]) upd(1, 1, n, 2 * b - it, n, a[it] + a[b]);
it--;
}
ans[i] = get(1, 1, n, l, r);
}
for(int i = 1; i <= nq; i++) cout << ans[i] << "\n";
}
컴파일 시 표준 에러 (stderr) 메시지
jumps.cpp: In function 'void build(int, int, int)':
jumps.cpp:18:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
18 | int mid = l + r >> 1;
| ~~^~~
jumps.cpp: In function 'void down(int)':
jumps.cpp:25:15: warning: pointer to a function used in arithmetic [-Wpointer-arith]
25 | if(!down[i]) return ;
| ^
jumps.cpp: In function 'void upd(int, int, int, int, int, int)':
jumps.cpp:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | int mid = l + r >> 1;
| ~~^~~
jumps.cpp: In function 'int get(int, int, int, int, int)':
jumps.cpp:54:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | int mid = l + r >> 1;
| ~~^~~
jumps.cpp: At global scope:
jumps.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
58 | main () {
| ^~~~
jumps.cpp: In function 'int main()':
jumps.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | freopen("task.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | freopen("wa.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |