제출 #570636

#제출 시각아이디문제언어결과실행 시간메모리
570636MohammadAghil3단 점프 (JOI19_jumps)C++14
100 / 100
1091 ms97644 KiB
#include <bits/stdc++.h> // #pragma GCC optimize ("Ofast,unroll-loops") // #pragma GCC target ("avx2") using namespace std; typedef long long ll; typedef pair<long double, ll> pp; #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl #define per(i,r,l) for(int i = (r); i >= (l); i--) #define rep(i,l,r) for(int i = (l); i < (r); i++) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() #define pb push_back #define ss second #define ff first void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll mod = 998244353, maxn = 5e5 + 5, lg = 19, inf = ll(1e9) + 5; ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;} ll a[maxn]; int n, q; void slv1_2(){ vector<vector<ll>> mx(n, vector<ll>(n, -inf)); rep(i,0,n){ mx[i][i] = a[i]; rep(j,i+1,n) mx[i][j] = max(mx[i][j-1], a[j]); } vector<vector<ll>> ans(n, vector<ll>(n, -inf)); rep(l,3,n+1){ rep(i,0,n-l+1){ int j = i + l - 1; ans[i][j] = max({ans[i+1][j], ans[i][j-1], a[i] + a[j] + mx[i+1][(i+j)>>1]}); } } while(q--){ int l, r; cin >> l >> r; cout << ans[--l][--r] << '\n'; } } template<class T> struct Rmq{ vector<vector<T>> rmq; vector<int> lgg; T comb(T a, T b){ return max(a, b); } Rmq(vector<T> a){ int n = sz(a); lgg.resize(n + 1); rep(i,2,n + 1) lgg[i] = lgg[i>>1] + 1; rmq.assign(lgg[n] + 1, vector<T>(n)); rmq[0] = a; rep(i,1,lgg[n] + 1){ rep(j,0,n-(1<<i)+1){ rmq[i][j] = comb(rmq[i-1][j], rmq[i-1][j + (1 << (i-1))]); } } } T get(int l, int r){ // 0-base [l, r] int g = lgg[r - l + 1]; return comb(rmq[g][l], rmq[g][r - (1<<g) + 1]); } }; void slv3(){ int l, r; cin >> l >> r; l--, r--, n = r - l + 1; vector<int> b(a + l, a + r + 1); Rmq<int> rmq(b); auto get_max = [&](int l, int r){ if(l > r || r < 0) return -1; l = max(0, l), r = min(r, n-1); return rmq.get(l, r); }; auto clc = [&](int i){ ll res = -inf; // right rep(j,0,i) res = max(res, 1ll*b[i] + b[j] + get_max(j-(i-j),j-1)); // center rep(j,0,i) res = max(res, 1ll*b[i] + b[j] + get_max(i+(i-j),n-1)); // left rep(j,i+1,n) res = max(res, 1ll*b[i] + b[j] + get_max(j+(j-i),n-1)); return res; }; vector<int> c(n); iota(all(c), 0), sort(all(c), [&](int i, int j){ return b[i] > b[j]; }); ll ans = 0; int g = min(int(log2(n))+3, n); rep(i,0,g){ ans = max(ans, clc(c[i])); } cout << ans << '\n'; } struct LazySegment{ vector<ll> seg, vl, laz; int n; void init(int _n, vector<ll> a = {}){ n = _n; seg.assign(n<<2, 0), laz.assign(n<<2, 0), vl.assign(n<<2, 0); // init if(sz(a)) build(a, 1, 0, n); } void updNode(int x, ll k){ seg[x] = max(vl[x] + k, seg[x]), laz[x] = max(laz[x], k); } void build(const vector<ll>& a, int x, int lx, int rx){ if(lx + 1 == rx){ seg[x] = vl[x] = a[lx]; return; } int mid = (lx + rx)>>1; build(a, x<<1, lx, mid), build(a, x<<1|1, mid, rx); seg[x] = vl[x] = max(seg[x<<1], seg[x<<1|1]); } void shift(int x){ if(laz[x]){ updNode(x<<1, laz[x]); updNode(x<<1|1, laz[x]); laz[x] = 0; } } void upd(int l, int r, ll a, int x, int lx, int rx){ if(l <= lx && r >= rx){ updNode(x, a); return; } if(l >= rx || r <= lx) return; shift(x); int mid = (lx + rx)>>1; upd(l, r, a, x<<1, lx, mid), upd(l, r, a, x<<1|1, mid, rx); seg[x] = max(seg[x<<1], seg[x<<1|1]); } void upd(int l, int r, ll a){ upd(l, r, a, 1, 0, n); } ll get(int l, int r, int x, int lx, int rx){ if(l <= lx && r >= rx) return seg[x]; if(l >= rx || r <= lx) return -1; // init shift(x); int mid = (lx + rx)>>1; return max(get(l, r, x<<1, lx, mid), get(l, r, x<<1|1, mid, rx)); } ll get(int l, int r){ return get(l, r, 1, 0, n); } }; void slv4(){ vector<vector<pp>> st(n); vector<ll> ans(q); rep(i,0,q){ int l, r; cin >> l >> r; l--, r--; st[l].pb({r, i}); } vector<int> stk; LazySegment seg; seg.init(n, vector<ll>(a, a + n)); per(i,n-1,0){ vector<int> candj; while(sz(stk) && a[stk.back()] < a[i]) candj.pb(stk.back()), stk.pop_back(); if(sz(stk)) candj.pb(stk.back()); stk.pb(i); for(int j: candj){ int k = j+j-i; if(k > n) continue; seg.upd(k, n, a[i] + a[j]); } for(auto[r,id]: st[i]) ans[id] = seg.get(i, r+1); } for(ll c: ans) cout << c << '\n'; } int main(){ cin.tie(0) -> sync_with_stdio(0); cin >> n; rep(i,0,n) cin >> a[i]; cin >> q; slv4(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In function 'void slv4()':
jumps.cpp:163:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  163 |           for(auto[r,id]: st[i]) ans[id] = seg.get(i, r+1);
      |                   ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...