fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define db long double
  4. #define sz(v) (int)v.size()
  5. #define all(v) v.begin(),v.end()
  6. #define rall(v) v.rbegin(),v.rend()
  7. #define fi first
  8. #define se second
  9. #define pb push_back
  10. #define pll pair<ll,ll>
  11. #define pii pair<int,int>
  12. #define fix(x,num) fixed << setprecision(num)<<x
  13.  
  14. using namespace std;
  15.  
  16. #include <ext/pb_ds/assoc_container.hpp>
  17. #include <ext/pb_ds/tree_policy.hpp>
  18. using namespace __gnu_pbds;
  19. template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  20. template<typename T>
  21. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  22.  
  23. string di[] = {"L", "R", "U", "D", "UR", "UL", "DR", "DL"};
  24. int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
  25. int dy[] = {-1, 1, 0, 0, 1, -1, 1, -1};
  26. const ll N =1e6+5,mod =998244353,inf =1e18;
  27.  
  28. struct sparse{
  29.     sparse(vector<ll>&v,ll n){
  30.         sset(v,n);
  31.     }
  32.  
  33.     vector<vector<pll>>tmx,tmn;
  34.     void sset(vector<ll>&v,ll n){
  35.         tmx=tmn=vector<vector<pll>>(n,vector<pll>(20));
  36.         for(int i=0;i<n;++i){
  37.             tmx[i][0]=tmn[i][0]={v[i],i};
  38.         }
  39.         for(int pw=1;(1<<pw)<=n;++pw){
  40.             for (int i = 0; i+(1<<pw) <=n ; ++i) {
  41.                 tmx[i][pw]=max(tmx[i][pw-1],tmx[i+(1<<(pw-1))][pw-1]);
  42.                 tmn[i][pw]=min(tmn[i][pw-1],tmn[i+(1<<(pw-1))][pw-1]);
  43.             }
  44.         }
  45.     }
  46.  
  47.     pll getmx(ll l,ll r){
  48.         if(r<l) swap(l,r);
  49.         ll z=log2(r-l+1);
  50.         return max(tmx[l][z],tmx[r-(1<<z)+1][z]);
  51.     }
  52.     pll getmn(ll l,ll r){
  53.         if(r<l) swap(l,r);
  54.         ll z=log2(r-l+1);
  55.         return min(tmn[l][z],tmn[r-(1<<z)+1][z]);
  56.     }
  57.  
  58.  
  59. };
  60.  
  61. vector<ll> calcPre(vector<ll>&v,ll n,ll k){
  62.     vector<ll>ret(sz(v));
  63.     stack<pll>s;
  64.     s.push({inf,k-1});
  65.     for (int i = k; i <=n ; ++i) {
  66.         ll cur=v[i]-v[i-k];
  67.         while(s.top().fi<=cur)
  68.             s.pop();
  69.         ret[i]=s.top().se-k+1;
  70.         s.push({cur,i});
  71.     }
  72.     return ret;
  73. }
  74.  
  75. vector<ll> calcSuf(vector<ll>&v,ll n,ll k){
  76.     vector<ll>ret(sz(v));
  77.     stack<pll>s;
  78.     s.push({inf,n+1});
  79.     for (int i = n; i >=k ; --i) {
  80.         ll cur=v[i]-v[i-k];
  81.         while(s.top().fi<=cur)
  82.             s.pop();
  83.         ret[i]=s.top().se;
  84.         s.push({cur,i});
  85.     }
  86.     return ret;
  87. }
  88.  
  89. void solve() {
  90.     ll n,k;  cin>>n>>k;
  91.     vector<ll>a(n+5),b(n+5);
  92.     for (int i = 1; i <=n ; ++i)  cin>>a[i];
  93.     for (int i = 1; i <=n ; ++i) {
  94.         cin >> b[i];
  95.         a[i] = b[i] - a[i];
  96.         a[i] += a[i - 1];
  97.         b[i] += b[i - 1];
  98.     }
  99.  
  100.     vector<ll>pre= calcPre(b,n,k),suf= calcSuf(b,n,k);
  101.     sparse s(a,n+5);
  102.  
  103.     ll ans=-inf;
  104.     for (int i = k; i <=n ; ++i) {
  105.         ll l=pre[i]+1,r=suf[i]-1;
  106.         l=s.getmn(l,i-k+1).se,r=s.getmx(i,r).se;
  107.         ans=max(ans,a[r]-a[l-1]-(b[i]-b[i-k]));
  108.     }
  109.     cout<<ans<<'\n';
  110.  
  111. }
  112.  
  113. int32_t main() {
  114.  
  115.     ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0);
  116.  
  117.     int testCases = 1;
  118.     cin >> testCases;
  119.  
  120.     for (int i = 1; i <=testCases ; ++i) {
  121.         // cout<<"Case "<<i<<":\n";
  122.         solve();
  123.     }
  124.  
  125.     return 0;
  126. }
  127.  
Success #stdin #stdout 0.01s 9248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1000000000000000000
https://ideone.com/qzVcRf
language:
C++ (gcc 8.3)
created:
28 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!