fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. int main() {
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.     int t;
  9.     if (!(cin >> t)) return 0;
  10.     while (t--) {
  11.         int n, q;
  12.         cin >> n >> q;
  13.         vector<ll> a(n+1), b(n+1);
  14.         for (int i = 1; i <= n; ++i) cin >> a[i];
  15.         for (int i = 1; i <= n; ++i) cin >> b[i];
  16.  
  17.         vector<ll> S(n+1), P(n+1);
  18.         P[0] = 0;
  19.         for (int i = 1; i <= n; ++i) {
  20.             S[i] = max(0LL, a[i]);
  21.             P[i] = P[i-1] + S[i];
  22.         }
  23.  
  24.         vector<ll> c(n+1);
  25.         for (int i = 1; i <= n; ++i) c[i] = b[i] - P[i];
  26.  
  27.         int LOG = 1;
  28.         while ((1 << LOG) <= n) ++LOG;
  29.         vector<int> lg(n+1);
  30.         lg[1] = 0;
  31.         for (int i = 2; i <= n; ++i) lg[i] = lg[i>>1] + 1;
  32.  
  33.         // sparse table st[k][i] = max on interval of length 2^k starting at i
  34.         vector<vector<ll>> st(LOG, vector<ll>(n+1, LLONG_MIN/4));
  35.         for (int i = 1; i <= n; ++i) st[0][i] = c[i];
  36.         for (int k = 1; k < LOG; ++k) {
  37.             int len = 1 << k;
  38.             int half = 1 << (k-1);
  39.             for (int i = 1; i + len - 1 <= n; ++i) {
  40.                 st[k][i] = max(st[k-1][i], st[k-1][i + half]);
  41.             }
  42.         }
  43.  
  44.         auto range_max = [&](int L, int R) -> ll {
  45.             int len = R - L + 1;
  46.             int k = lg[len];
  47.             return max(st[k][L], st[k][R - (1<<k) + 1]);
  48.         };
  49.  
  50.         while (q--) {
  51.             ll k0; int l, r;
  52.             cin >> k0 >> l >> r;
  53.             ll Sseg = P[r] - P[l-1];
  54.             ll bestC = range_max(l, r);
  55.             ll Mseg = P[r] + bestC;
  56.             ll ans = max(k0 + Sseg, Mseg);
  57.             cout << ans << '\n';
  58.         }
  59.     }
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/NaxOEF
language:
C++ (gcc 8.3)
created:
14 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!