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.     int a,b,c;
  135.     cin>>a>>b>>c;
  136.     cout<<a-c+b<<endl;
  137.     return 0;
  138. }
  139.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1104595667
https://ideone.com/kUrRZc
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!