제출 #1097243

#제출 시각아이디문제언어결과실행 시간메모리
1097243LeDaiKing3단 점프 (JOI19_jumps)C++14
100 / 100
657 ms72132 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define pb push_back #define ALL(n) n.begin(), n.end() #define mask(n) (1ll << (n)) #define ck(n, k) (((n) >> (k))&1) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int a[500005], nxt[500005]; vector<pair<int,int>> query[500005]; ll st[2000005], laz[2000005]; int s[5000005]; ll ans[500005]; void down(int id) { ll &val = laz[id]; if (val == 0) return; st[id * 2] = max(st[id * 2], s[id * 2] + val); laz[id * 2] = max(laz[id * 2], val); st[id * 2 + 1] = max(st[id * 2 + 1], s[id * 2 + 1] + val); laz[id * 2 + 1] = max(laz[id * 2 + 1], val); val = 0; } void update(int id, int l, int r, int u, int v, ll val) { if (r < u || l > v) return; if (u <= l && r <= v) { st[id] = max(st[id], s[id] + val); laz[id] = max(laz[id], val); return; } int mid = (l + r)/2; down(id); update(id * 2, l, mid, u, v, val); update(id * 2 + 1, mid + 1, r, u, v, val); st[id] = max(st[id * 2], st[id * 2 + 1]); // cout << l << " " << r << " " << st[id] << endl; } ll get(int id, int l, int r, int u, int v) { if (r < u || l > v) return 0; if (u <= l && r <= v) { return st[id]; } int mid = (l + r)/2; down(id); return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v)); // cout << "wtf " << " " << l << " " << r << endl; } void build(int id, int l, int r) { if (l > r) return; if (l == r) { s[id] = a[l]; return; } int mid = (l + r) / 2; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); s[id] = max(s[id * 2], s[id * 2 + 1]); // cout << l << " " << r << " " << s[id] << endl; } void solution() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } build(1, 1, n); int q; cin >> q; for (int i = 1; i <= q; i++) { int l, r; cin >> l >> r; query[l].pb({r, i}); } stack<int> st; for (int i = n; i; i--) { while(!st.empty() && a[st.top()] <= a[i]) st.pop(); nxt[i] = (st.empty() ? -1 : st.top()); // cout << nxt[i] << endl; st.push(i); if (i == n) continue; int j = i + 1; while(j != -1) { if (2 * j - i <= n) { update(1, 1, n, 2 * j - i, n, a[i] + a[j]); // cout << i << " " << j << endl; } if (a[j] >= a[i]) break; j = nxt[j]; } for (auto v : query[i]) { // cout << i << " " << v.fi << endl; ans[v.se] = get(1, 1, n, i, v.fi); } } for (int i = 1; i <= q; i++) cout << ans[i] << "\n"; } int main() { //freopen("test.inp", "r", stdin); //freopen("test.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solution(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...