Submission #1102123

#TimeUsernameProblemLanguageResultExecution timeMemory
1102123ro9669Triple Jump (JOI19_jumps)C++17
100 / 100
735 ms70988 KiB
#include <bits/stdc++.h> #define fi first #define se second #define all(v) v.begin() , v.end() #define sz(v) int(v.size()) #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin()); using namespace std; typedef long long ll; typedef pair<int , int> ii; typedef pair<long long , int> lli; const int maxN = int(5e5)+7; int n , q , a[maxN] , res[maxN]; vector<ii> query[maxN]; struct node{ int lazy , base , val; node(){ lazy = base = val = 0; } } st[4 * maxN]; #define lef(id) id * 2 #define rig(id) id * 2 + 1 void build(int id , int l , int r){ if (l == r){ st[id].base = a[l]; return; } int mid = (l + r) / 2; build(lef(id) , l , mid); build(rig(id) , mid + 1 , r); st[id].base = max(st[lef(id)].base , st[rig(id)].base); } void modify(int id , int x){ st[id].lazy = max(st[id].lazy , x); st[id].val = max(st[id].val , st[id].base + x); } void down(int id , int l , int r){ int &x = st[id].lazy; if (l == r) return; modify(lef(id) , x); modify(rig(id) , x); } void update(int id , int l , int r , int u , int v , int x){ if (v < l || r < u) return; if (u <= l && r <= v) return modify(id , x); down(id , l , r); int mid = (l + r) / 2; update(lef(id) , l , mid , u , v , x); update(rig(id) , mid + 1 , r , u , v , x); st[id].val = max(st[lef(id)].val , st[rig(id)].val); } int get(int id , int l , int r , int u , int v){ if (v < l || r < u) return 0; if (u <= l && r <= v) return st[id].val; down(id , l , r); int mid = (l + r) / 2; return max(get(lef(id) , l , mid , u , v) , get(rig(id) , mid + 1 , r , u , v)); } void update(int x , int y){ int z = 2 * y - x; update(1 , 1 , n , z , n , a[x] + a[y]); } void solve(){ 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].push_back({r , i}); } deque<int> dq; for (int i = n ; i >= 1 ; i--){ while (dq.empty() == 0 && a[i] >= a[dq.back()]){ update(i , dq.back()); dq.pop_back(); } if (dq.empty() == 0) update(i , dq.back()); for (auto it : query[i]){ res[it.se] = get(1 , 1 , n , i , it.fi); } dq.push_back(i); } for (int i = 1 ; i <= q ; i++) cout << res[i] << "\n"; } #define name "A" int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(name".INP" , "r")){ freopen(name".INP" , "r" , stdin); freopen(name".OUT" , "w" , stdout); } int t = 1; //cin >> t; while (t--) solve(); return 0; }

Compilation message (stderr)

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