Submission #197729

#TimeUsernameProblemLanguageResultExecution timeMemory
197729HellAngelTriple Jump (JOI19_jumps)C++14
100 / 100
1331 ms99576 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 5e5 + 7; stack<int> st; int n, m, a[maxn], ans[maxn]; vector<pair<int, int>> q[maxn]; vector<int> p[maxn]; struct Node { int l, r, ans; Node(){}; Node(int l, int r, int ans): l(l), r(r), ans(ans) {}; Node operator + (const Node &other) const { Node cc; cc.l = max(l, other.l); cc.r = max(r, other.r); cc.ans = max({ans, other.ans, l + other.r}); return cc; } } IT[4 * maxn]; void Build(int id, int l, int r) { if(l == r) { IT[id].r = a[l]; return; } int mid = l + r >> 1; Build(id * 2, l, mid); Build(id * 2 + 1, mid + 1, r); IT[id] = IT[id * 2] + IT[id * 2 + 1]; } void Update(int id, int l, int r, int u, int val) { if(l == r) { IT[id].l = max(IT[id].l, val); return; } int mid = l + r >> 1; if(u <= mid) Update(id * 2, l, mid, u, val); else Update(id * 2 + 1, mid + 1, r, u, val); IT[id] = IT[id * 2] + IT[id * 2 + 1]; } Node Query(int id, int l, int r, int u, int v) { if(l > v || r < u) return {0, 0, 0}; if(u <= l && r <= v) { return IT[id]; } int mid = l + r >> 1; return Query(id * 2, l, mid, u, v) + Query(id * 2 + 1, mid + 1, r, u, v); } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout); cin >> n; /// first we need to list all the potential pair for 2 elements (a, b) /// if it exists k such that a < k < b and a[k] > a[b], (a, b) will not the optimal pair we need because we can choose (a, k) for a better solution /// in the same way if it exists k such that a < k < b and a[a] < a[k] < a[b], (a, b) will not the optimal pair we need because we can choose (k, b) for a better solution /// => for every k such that a < k < b, there must be a[a] > a[k] and a[k] < a[b] for(int i = 1; i <= n; i++) { cin >> a[i]; while(!st.empty() && a[st.top()] <= a[i]) { p[st.top()].push_back(i); st.pop(); } if(!st.empty()) p[st.top()].push_back(i); st.push(i); } Build(1, 1, n); cin >> m; for(int i = 1; i <= m; i++) { int u, v; cin >> u >> v; q[u].emplace_back(v, i); } for(int i = n; i >= 1; i--) { for(auto j: p[i]) { int cc = 2 * j - i - 1; if(cc <= n) Update(1, 1, n, cc, a[i] + a[j]); } for(auto j: q[i]) { ans[j.second] = Query(1, 1, n, i, j.first).ans; } } for(int i = 1; i <= m; i++) cout << ans[i] << '\n'; }

Compilation message (stderr)

jumps.cpp: In function 'void Build(long long int, long long int, long long int)':
jumps.cpp:34:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
jumps.cpp: In function 'void Update(long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:47:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
jumps.cpp: In function 'Node Query(long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:60:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
jumps.cpp: In function 'int32_t main()':
jumps.cpp:68:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:68:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...