Submission #1114597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114597		mychecksedad	Triple Jump (JOI19_jumps)	C++17	100 / 100	785 ms	223160 KiB

jumps

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 2e6+100, M = 1e5+10, K = 22, MX = 30;


struct Fenwick{
  int n;
  vector<int> t;
  Fenwick(int _n){
    n = _n;
    t.resize(n+1, 0);
  }
  void add(int v){
    while(v <= n){
      t[v]++;
      v += (v&-v);
    }
  }
  int get(int v){
    int res = 0;
    while(v > 0){
      res += t[v];
      v -= (v&-v);
    }
    return res;
  }
};
 
int n, a[N], q, L[N], R[N], rmq[N][K], go[N], T[N], C[N], ans[N], COMB[N];
vector<pii> Q[N], to[N];
int comb(int x, int y){
  return max(x,y);
}
int get(int l, int r){
  int k = int(log2(r-l+1));
  return max(rmq[l][k], rmq[r-(1<<k)+1][k]);
}
void build(int l, int r, int k){
  C[k] = 0;
  if(l == r){
    T[k] = a[l];
    COMB[k] = a[l];
    return;
  }
  int m = l+r>>1;
  build(l, m, k<<1);
  build(m+1, r, k<<1|1);
  COMB[k] = comb(COMB[k<<1], COMB[k<<1|1]);
  T[k] = comb(T[k<<1], T[k<<1|1]);
}
int get_max(int l, int r, int ql, int qr, int k){
  if(ql > r || l > qr) return 0;
  if(ql <= l && r <= qr) return max(COMB[k], T[k]+C[k]);
  C[k<<1] = max(C[k<<1], C[k]);
  C[k<<1|1] = max(C[k<<1|1], C[k]);
  int m = l+r>>1;
  auto v = comb(get_max(l, m, ql, qr, k<<1), get_max(m+1, r, ql, qr, k<<1|1));
  return v;
}
void upd(int l, int r, int ql, int qr, int k, int val){
  if(ql > r || l > qr) return;
  if(ql <= l && r <= qr){
    C[k] = max(val, C[k]);
    COMB[k] = max(COMB[k], C[k] + T[k]);
    // cout << COMB[k] << '\n';
    return;
  }
  C[k<<1] = max(C[k<<1], C[k]);
  C[k<<1|1] = max(C[k<<1|1], C[k]);
  int m = l+r>>1;
  upd(l, m, ql, qr, k<<1, val);
  upd(m+1, r, ql, qr, k<<1|1, val);
  COMB[k] = max({COMB[k<<1], COMB[k<<1|1], C[k] + T[k]});
  // cout << COMB[k] << ' '<< l << ' ' << r << '\n';
}

void solve(){
  cin >> n;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
    rmq[i][0] = a[i];
  }
  deque<int> A;
  for(int i = 1; i <= n; ++i){
    while(A.size() && a[A.back()] < a[i]) A.pop_back();
    L[i] = A.size() == 0 ? - 1 : A.back();
    A.pb(i);
    if(L[i] > -1){
      to[L[i]].pb({a[i] + a[L[i]], i + i - L[i]});
    }
  }
  A.clear();
  for(int i = n; i >= 1; --i){
    while(A.size() && a[A.back()] < a[i]) A.pop_back();
    R[i] = A.size() == 0 ? - 1 : A.back();
    A.pb(i);
    if(R[i] > -1)
      to[i].pb({a[i] + a[R[i]], R[i] + R[i] - i});
  }
  for(int j = 1; j < K; ++j){
    for(int i = 1; i + (1<<j) <= n + 1; ++i){
      rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
    }
  }
  build(1, n, 1);
  cin >> q;
  for(int i = 1; i <= q; ++i){
    int l, r; cin >> l >> r;
    Q[l].pb({r, i});
  }
  for(int i = n; i >= 1; --i){
    for(auto p: to[i]){
      if(p.ss <= n){
        // cout << p.ff << ' ' << p.ss << ' ' << i << '\n';
        upd(1, n, p.ss, n, 1, p.ff);
      }
    }
    for(auto p: Q[i]){
      ans[p.ss] = get_max(1, n, i, p.ff, 1);
    }
  }
  for(int i = 1; i <= q; ++i){
    cout << ans[i] << '\n';
  }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

Compilation message (stderr)

jumps.cpp: In function 'void build(int, int, int)':
jumps.cpp:56:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |   int m = l+r>>1;
      |           ~^~
jumps.cpp: In function 'int get_max(int, int, int, int, int)':
jumps.cpp:67:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |   int m = l+r>>1;
      |           ~^~
jumps.cpp: In function 'void upd(int, int, int, int, int, int)':
jumps.cpp:81:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |   int m = l+r>>1;
      |           ~^~
jumps.cpp: In function 'int main()':
jumps.cpp:141:15: warning: unused variable 'aa' [-Wunused-variable]
  141 |   int tt = 1, aa;
      |               ^~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54