Submission #998572

#TimeUsernameProblemLanguageResultExecution timeMemory
998572Beerus13Triple Jump (JOI19_jumps)C++17
100 / 100
811 ms78804 KiB
#include<bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i) #define FORD(i, b, a) for(int i = (b), _a = (a); i >= _a; --i) #define REP(i, a, b) for(int i = (a), _b = (b); i < _b; ++i) #define REPD(i, b, a) for(int i = (b), _a = (a); i > _a; --i) #define MASK(i) (1LL << (i)) #define BIT(mask, i) (((mask) >> (i)) & 1) #define __builtin_popcount __builtin_popcountll #define all(v) v.begin(), v.end() #define ll long long #define ull unsigned long long #define pii pair<int, int> #define fi first #define se second mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll Rand(ll l, ll r) {return l + (ull) rng() % (r - l + 1);} template<class X, class Y> bool minimize(X &x, const Y &y) { if (x > y) { x = y; return true; } else return false; } template<class X, class Y> bool maximize(X &x, const Y &y) { if (x < y) { x = y; return true; } else return false; } template<class T> T Abs(const T &x) { return (x < 0 ? -x : x); } const int N = 5e5 + 5; const int inf = 1e9; struct node { int res, mx, lz; node() { res = mx = lz = 0; } }; int n, q, a[N]; vector<pii> qrs[N]; vector<pii> candidates; node st[N << 2]; void push(int id, int x) { maximize(st[id].lz, x); maximize(st[id].res, st[id].mx + x); } void down(int id) { if(!st[id].lz) return; push(id << 1, st[id].lz); push(id << 1 | 1, st[id].lz); st[id].lz = 0; } void upd_point(int u, int x) { int id = 1, l = 1, r = n; while(l ^ r) { down(id); int m = l + r >> 1; if(u > m) id = id << 1 | 1, l = m + 1; else id = id << 1, r = m; } st[id].mx = x; while(id > 1) id >>= 1, st[id].mx = max(st[id << 1].mx, st[id << 1 | 1].mx); } void update(int u, int v, int x, int id = 1, int l = 1, int r = n) { if(u > r || v < l) return; if(u <= l && r <= v) { push(id, x); return; } down(id); int m = l + r >> 1; update(u, v, x, id << 1, l, m); update(u, v, x, id << 1 | 1, m + 1, r); st[id].res = max(st[id << 1].res, st[id << 1 | 1].res); } int query(int u, int v, int id = 1, int l = 1, int r = n) { if(u > r || v < l) return 0; if(u <= l && r <= v) return st[id].res; down(id); int m = l + r >> 1; return max(query(u, v, id << 1, l, m), query(u, v, id << 1 | 1, m + 1, r)); } void process() { cin >> n; FOR(i, 1, n) cin >> a[i]; cin >> q; REP(i, 0, q) { int l, r; cin >> l >> r; qrs[l].emplace_back(r, i); } vector<int> stk; FOR(i, 1, n) { while(!stk.empty() && a[stk.back()] < a[i]) stk.pop_back(); if(stk.size()) candidates.emplace_back(stk.back(), i); stk.push_back(i); } while(!stk.empty()) stk.pop_back(); FORD(i, n, 1) { while(!stk.empty() && a[stk.back()] < a[i]) stk.pop_back(); if(stk.size()) candidates.emplace_back(i, stk.back()); stk.push_back(i); } sort(all(candidates)); vector<int> ans(q); FORD(i, n, 1) { upd_point(i, a[i]); while(!candidates.empty() && candidates.back().fi == i) { auto [l, r] = candidates.back(); candidates.pop_back(); update(2 * r - l, n, a[l] + a[r]); } for(auto [r, id] : qrs[i]) { ans[id] = query(i, r); } } for(auto x : ans) cout << x << '\n'; } signed main() { if(fopen("test.inp","r")) { freopen("test.inp","r",stdin); freopen("test.out","w",stdout); } ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int ntests = 1; // cin >> ntests; while(ntests--) process(); return 0; } // https://oj.uz/problem/view/JOI19_jumps

Compilation message (stderr)

jumps.cpp: In function 'void upd_point(int, int)':
jumps.cpp:69:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int m = l + r >> 1;
      |                 ~~^~~
jumps.cpp: In function 'void update(int, int, int, int, int, int)':
jumps.cpp:84:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |     int m = l + r >> 1;
      |             ~~^~~
jumps.cpp: In function 'int query(int, int, int, int, int)':
jumps.cpp:94:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |     int m = l + r >> 1;
      |             ~~^~~
jumps.cpp: In function 'int main()':
jumps.cpp:138:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:139:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |         freopen("test.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...