제출 #749431

#제출 시각아이디문제언어결과실행 시간메모리
749431He_Huanglu3단 점프 (JOI19_jumps)C++17
100 / 100
1030 ms72024 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...