Submission #1229594

#TimeUsernameProblemLanguageResultExecution timeMemory
1229594hainam2k9Triple Jump (JOI19_jumps)C++20
100 / 100
667 ms76900 KiB
#include <bits/stdc++.h> #define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0) #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout) #define ll long long #define ull unsigned long long #define i128 __int128 #define db long double #define sz(a) ((int)(a).size()) #define pb emplace_back #define pf emplace_front #define pob pop_back #define pof pop_front #define lb lower_bound #define ub upper_bound #define fi first #define se second #define ins emplace #define mp make_pair using namespace std; const int MOD = 1e9+7, MAXN = 5e5+5; const string NAME = ""; int n,q,a[MAXN],rs[MAXN]; int sgt[MAXN<<2],lazy[MAXN<<2],MAX[MAXN<<2]; vector<int> v[MAXN]; vector<pair<int,int>> query[MAXN]; stack<int> st; void build(int id, int l, int r){ if(l==r) return sgt[id]=MAX[id]=a[l], void(); int mid=(l+r)>>1; build(id<<1,l,mid); build(id<<1|1,mid+1,r); sgt[id]=MAX[id]=max(sgt[id<<1],sgt[id<<1|1]); } inline void down(int id){ lazy[id<<1]=max(lazy[id<<1],lazy[id]), sgt[id<<1]=max(sgt[id<<1],lazy[id<<1]+MAX[id<<1]); lazy[id<<1|1]=max(lazy[id<<1|1],lazy[id]), sgt[id<<1|1]=max(sgt[id<<1|1],lazy[id<<1|1]+MAX[id<<1|1]); } void update(int id, int l, int r, int u, int v, int val){ if(v<l||r<u||u>v) return; if(u<=l&&r<=v){ lazy[id]=max(lazy[id],val); sgt[id]=max(sgt[id],lazy[id]+MAX[id]); return; } down(id); int mid=(l+r)>>1; update(id<<1,l,mid,u,v,val); update(id<<1|1,mid+1,r,u,v,val); sgt[id]=max(sgt[id<<1],sgt[id<<1|1]); } int getmax(int id, int l, int r, int u, int v){ if(v<l||r<u||u>v) return 0; if(u<=l&&r<=v) return sgt[id]; down(id); int mid=(l+r)>>1; return max(getmax(id<<1,l,mid,u,v),getmax(id<<1|1,mid+1,r,u,v)); } int main() { tt; if(fopen((NAME + ".INP").c_str(), "r")) fo; cin >> n; for(int i = 1; i<=n; ++i) cin >> a[i]; build(1,1,n); cin >> q; for(int i = 1; i<=q; ++i){ int l,r; cin >> l >> r; query[l].pb(r,i); } for(int i = 1; i<=n; ++i){ while(!st.empty()&&a[i]>=a[st.top()]) v[st.top()].pb(i), st.pop(); if(!st.empty()) v[st.top()].pb(i); st.push(i); } for(int i = n-2; i>0; --i){ for(int& j : v[i]) update(1,1,n,j*2-i,n,a[i]+a[j]); for(pair<int,int>& p : query[i]) rs[p.se]=getmax(1,1,n,i,p.fi); } for(int i = 1; i<=q; ++i) cout << rs[i] << "\n"; }

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:3:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:61:45: note: in expansion of macro 'fo'
   61 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~
jumps.cpp:3:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |                                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:61:45: note: in expansion of macro 'fo'
   61 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...