Submission #1241964

#TimeUsernameProblemLanguageResultExecution timeMemory
1241964khoile08Triple Jump (JOI19_jumps)C++17
32 / 100
138 ms28340 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = a; i <= b; i++) #define FOD(i, a, b) for(int i = a; i >= b; i--) #define fi first #define se second #define ll long long #define db double #define ii pair<int,int> #define pb push_back #define MASK(i) (1LL << i) #define sq(i) (1LL * (i) * (i)) #define task "khoile08" const ll INF = 1e18; const int inf = 1e9; const int N = 5e5; int n, q; int a[N + 5]; vector<ii> query[N + 5]; struct Smt { ll sum[4 * N + 5], mx[4 * N + 5], ans[4 * N + 5], lz[4 * N + 5]; void build(int id, int l, int r) { if(l == r) { mx[id] = a[l]; return; } int mid = l + r >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); mx[id] = max(mx[id << 1], mx[id << 1 | 1]); } void push(int id) { ll val = lz[id]; ans[id << 1] = max(ans[id << 1], val + mx[id << 1]); ans[id << 1 | 1] = max(ans[id << 1 | 1], val + mx[id << 1 | 1]); lz[id << 1] = max(lz[id << 1], val); lz[id << 1 | 1] = max(lz[id << 1 | 1], val); lz[id] = 0; return; } void up(int id, int l, int r, int u, int v, ll val) { if(l > v || r < u) return; if(l >= u && r <= v) { ans[id] = max(ans[id], val + mx[id]); lz[id] = max(lz[id], val); return; } push(id); int mid = l + r >> 1; up(id << 1, l, mid, u, v, val); up(id << 1 | 1, mid + 1, r, u, v, val); ans[id] = max(ans[id << 1], ans[id << 1 | 1]); } ll get(int id, int l, int r, int u, int v) { if(l > v || r < u) return -INF; if(l >= u && r <= v) return ans[id]; push(id); int mid = l + r >> 1; return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v)); } }; Smt it; stack<int> st; ll res[N]; void Solve() { it.build(1, 1, n); FOD(i, n, 1) { while(!st.empty() && a[st.top()] < a[i]) { int y = st.top(); it.up(1, 1, n, 2 * y - i, n, a[i] + a[y]); st.pop(); } if(st.size()) it.up(1, 1, n, 2 * st.top() - i, n, a[i] + a[st.top()]); st.push(i); for(auto H : query[i]) { res[H.se] = it.get(1, 1, n, i, H.fi); } } FOR(i, 1, q) cout << res[i] << '\n'; } signed main() { if(fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tc = 1; // cin >> tc; while(tc--) { cin >> n; FOR(i, 1, n) cin >> a[i]; cin >> q; FOR(i, 1, q) { int l, r; cin >> l >> r; query[l].pb({r, i}); } Solve(); } }

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:92:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |                 freopen(task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:93:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |                 freopen(task".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...