fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. #define saleh                         \
  8.     ios_base::sync_with_stdio(false); \
  9.     cin.tie(nullptr);
  10. #define ll long long
  11.  
  12. struct node
  13. {
  14.     ll sum, pre, suff, mx;
  15.     node(ll x = 0)
  16.     {
  17.         sum = pre = suff = mx = x;
  18.     }
  19.     void change(ll x)
  20.     {
  21.         sum = pre = suff = mx = x;
  22.     }
  23. };
  24.  
  25. struct segTree
  26. {
  27.     int size;
  28.     vector<node> segData;
  29.  
  30.     void build(int n)
  31.     {
  32.         size = 1;
  33.         while (size < n)
  34.             size *= 2;
  35.         segData.resize(2 * size);
  36.     }
  37.  
  38.     node merge(node l, node r)
  39.     {
  40.         node res;
  41.         res.mx = max({l.mx, r.mx, l.suff + r.pre});
  42.         res.pre = max(l.pre, l.sum + r.pre);
  43.         res.suff = max(r.suff, r.sum + l.suff);
  44.         res.sum = l.sum + r.sum;
  45.         return res;
  46.     }
  47.  
  48.     void build(vector<ll> &v, int x, int lx, int rx)
  49.     {
  50.         if (rx - lx == 1)
  51.         {
  52.             if (lx < (int)v.size())
  53.             {
  54.                 segData[x] = node(v[lx]);
  55.             }
  56.             return;
  57.         }
  58.         int mid = (lx + rx) / 2;
  59.         build(v, 2 * x + 1, lx, mid);
  60.         build(v, 2 * x + 2, mid, rx);
  61.         segData[x] = merge(segData[2 * x + 1], segData[2 * x + 2]);
  62.     }
  63.  
  64.     void build(vector<ll> &v)
  65.     {
  66.         build(v, 0, 0, size);
  67.     }
  68.  
  69.     node range(int l, int r, int x, int lx, int rx)
  70.     {
  71.         if (lx >= r || rx <= l)
  72.             return node(0);
  73.         if (lx >= l && rx <= r)
  74.             return segData[x];
  75.  
  76.         int mid = (lx + rx) / 2;
  77.         node lef = range(l, r, 2 * x + 1, lx, mid);
  78.         node right = range(l, r, 2 * x + 2, mid, rx);
  79.         return merge(lef, right);
  80.     }
  81.  
  82.     ll range(int l, int r)
  83.     {
  84.         return range(l, r, 0, 0, size).mx;
  85.     }
  86.  
  87.     node full_range(int l, int r)
  88.     {
  89.         return range(l, r, 0, 0, size);
  90.     }
  91. };
  92.  
  93. void solve(
  94.     vector<ll> &c, vector<ll> &e, vector<pair<int, int>> &br, int k)
  95. {
  96.     // c is b - a
  97.     // e is the (n-k) segments
  98.     int n = c.size() + 1;
  99.     segTree segment;
  100.     segment.build(n);
  101.     segment.build(c);
  102.  
  103.     // zero based , right + 1
  104.     //(left to LeftStartIndForD)
  105.     //(RightEndIndForDPlus1 to right)
  106.     ll ans = LLONG_MIN;
  107.     for (int i = 0; i < e.size(); i++)
  108.     {
  109.         ll total_sum = segment.full_range(i, i + k).sum;
  110.         // cout << "Sum from " << LeftStartIndForD << " to " << RightEndIndForDPlus1 << " = " << total_sum << '\n';
  111.         ll tmp = total_sum;
  112.  
  113.         ll maxPre = segment.full_range(br[i].first, i).suff;
  114.         // cout << maxPre << '\n';
  115.         tmp += maxPre;
  116.  
  117.         ll maxSuff = segment.full_range(i + k, br[i].second + 1).pre;
  118.         // cout<<"suf"<<i+k<<" "<<br[i].second+1<<endl;
  119.         // cout << maxSuff << '\n';
  120.         tmp += maxSuff;
  121.         ans = max(ans, tmp - e[i]);
  122.         // cout<<i<<" to "<<i+k-1<<endl;
  123.         // cout<<"sum : "<<total_sum<<endl;
  124.         // cout<<"maxPre : "<<maxPre<<endl;
  125.         // cout<<"maxSuff : "<<maxSuff<<endl;
  126.     }
  127.  
  128.     cout << ans << '\n';
  129. }
  130.  
  131. int main()
  132. {
  133.     saleh;
  134.  
  135.     int t;
  136.     cin >> t;
  137.     while (t--)
  138.     {
  139.         int n, k;
  140.         cin >> n >> k;
  141.  
  142.         vector<ll> a(n), b(n), c(n);
  143.         for (int i = 0; i < n; i++)
  144.         {
  145.             cin >> a[i];
  146.         }
  147.         for (int i = 0; i < n; i++)
  148.         {
  149.             cin >> b[i];
  150.             c[i] = b[i] - a[i];
  151.         }
  152.  
  153.         vector<ll> sumbk(n - k + 1);
  154.  
  155.         ll bsum = 0;
  156.         int l = 0, r = 0;
  157.         while (r < k)
  158.         {
  159.             bsum += b[r++];
  160.         }
  161.         sumbk[0] = bsum;
  162.  
  163.         while (r < n)
  164.         {
  165.             bsum -= b[l++];
  166.             bsum += b[r++];
  167.             sumbk[l] = bsum;
  168.         }
  169.  
  170.         vector<pair<int, int>> br(n - k + 1);
  171.         stack<pair<ll, int>> s1, s2;
  172.  
  173.         s1.push({sumbk[0], 0});
  174.         br[0].first = 0;
  175.  
  176.         for (int i = 1; i < n - k + 1; i++)
  177.         {
  178.             while (!s1.empty() && s1.top().first <= sumbk[i])
  179.                 s1.pop();
  180.  
  181.             if (s1.empty())
  182.             {
  183.                 br[i].first = 0;
  184.             }
  185.             else
  186.             {
  187.                 br[i].first = s1.top().second + 1;
  188.             }
  189.             s1.push({sumbk[i], i});
  190.         }
  191.  
  192.         s2.push({sumbk[n - k], n - k});
  193.         br[n - k].second = n - 1;
  194.  
  195.         for (int i = n - k - 1; i >= 0; i--)
  196.         {
  197.             while (!s2.empty() && s2.top().first <= sumbk[i])
  198.                 s2.pop();
  199.  
  200.             if (s2.empty())
  201.             {
  202.                 br[i].second = n - 1;
  203.             }
  204.             else
  205.             {
  206.                 br[i].second = s2.top().second - 2 + k;
  207.             }
  208.             s2.push({sumbk[i], i});
  209.         }
  210.         solve(c, sumbk, br, k);
  211.     }
  212.  
  213.     return 0;
  214. }
  215.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1xwNqU
language:
C++ (gcc 8.3)
created:
6 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!