fork download
copy 
  1. # include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define Roxy "minmax"
  5.  
  6. bool mtt = 0;
  7. int test = 1;
  8.  
  9. #define             ll  long long
  10. #define             db double
  11. #define             ve  vector
  12. #define             vi  vector<int>
  13. #define            str  string
  14. #define             pb  push_back
  15. #define             el  '\n'
  16. #define            pii  pair<int,int>
  17. #define            pli  pair<ll,int>
  18. #define             mp  make_pair
  19. #define             fi  first
  20. #define             se  second
  21. #define         UNI(a)  sort(ALL(a)),a.resize(unique(ALL(a))-a.begin())
  22. #define     FOR(i,a,b)  for(int i=(int)(a);i<=(int)(b);i++)
  23. #define    FORD(i,a,b)  for(int i=(int)(a);i>=(int)(b);i--)
  24. #define    FORN(i,a,b)  for(int i=(int)(a);i<(int)(b);i++)
  25. #define         ALL(a)  a.begin(),a.end()
  26. #define             LB  lower_bound
  27. #define             UB  upper_bound
  28. #define            tct  template<class T>
  29. #define     BIT(msk,i)  (msk>>(i)&1)
  30. #define        MASK(i)  (1ll<<(i))
  31. #define          SZ(_)  (int)(_.size())
  32. #define           btpc  __builtin_popcountll
  33. ll lg(ll a){return __lg(a);}
  34. ll sq(ll a){return a*a;}
  35. ll gcd(ll a,ll b){return __gcd(a,b);}
  36. ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
  37. ll rd(ll l , ll r ){return l+1LL*rand()*rand()%(r-l+1);}
  38. #define prt(a,n) FOR(_i,1,n)cout<<a[_i]<<" ";cout<<el;
  39. #define prv(a) for(auto _v:a)cout<<_v<<" "; cout<<el;
  40.  
  41. tct bool mini(T& a,T b){return (a>b)?a=b,1:0;}
  42. tct bool maxi(T& a,T b){return (a<b)?a=b,1:0;}
  43.  
  44. int xx[] = {0,-1,0,1} ;
  45. int yy[] = {-1,0,1,0} ;
  46.  
  47. const db PI = acos(-1), EPS = 1e-9;
  48. const ll inf = 1e18, cs = 331, sm = 1e9+7;
  49. const int N = 2e5+5, oo = 2e9, LG = __lg(N) + 1;
  50.  
  51. int n, q;
  52. int a[N], d[N];
  53.  
  54. // Chia dãy thành các đoạn đồng biến
  55.  
  56. void init() {
  57.     cin >> n >> q;
  58.     FOR(i, 1, n) cin >> a[i];
  59.     FOR(i, 1, n - 1) d[i] = a[i + 1] - a[i];
  60. }
  61.  
  62. struct Node {
  63.     ll dp[2][2];
  64.     int head, tail;
  65. } st[4 * N];
  66.  
  67. Node merge(Node a, Node b) {
  68.     if(a.head == 0) return b;
  69.     if(b.head == 0) return a;
  70.  
  71.     Node ans;
  72.  
  73.     ans.dp[0][0] = max({a.dp[0][1] + b.dp[0][0], a.dp[0][0] + b.dp[1][0]});
  74.     ans.dp[1][0] = max({a.dp[1][1] + b.dp[0][0], a.dp[1][0] + b.dp[1][0]});
  75.     ans.dp[0][1] = max({a.dp[0][1] + b.dp[0][1], a.dp[0][0] + b.dp[1][1]});
  76.     ans.dp[1][1] = max({a.dp[1][0] + b.dp[0][1], a.dp[1][1] + b.dp[0][1], a.dp[1][0] + b.dp[1][1]});
  77.  
  78.     if(a.tail == b.head) {
  79.         ans.dp[0][0] = max(ans.dp[0][0], a.dp[0][1] + b.dp[1][0]);
  80.         ans.dp[0][1] = max(ans.dp[0][1], a.dp[0][1] + b.dp[1][1]);
  81.         ans.dp[1][0] = max(ans.dp[1][0], a.dp[1][1] + b.dp[1][0]);
  82.         ans.dp[1][1] = max(ans.dp[1][1], a.dp[1][1] + b.dp[1][1]);
  83.     }
  84.     ans.head = a.head;
  85.     ans.tail = b.tail;
  86.     return ans;
  87. }
  88.  
  89. void up(int id, int l, int r, int pos, int val) {
  90.     if(pos < l || pos > r)
  91.         return;
  92.     if(l == r) {
  93.         d[l]+= val;
  94.  
  95.         st[id].dp[1][1] = abs(d[l]);
  96.         st[id].tail = st[id].head = (d[l] >= 0 ? 1 : - 1);
  97.         return;
  98.     }
  99.     int mid = (l + r) / 2;
  100.     up(id << 1, l, mid, pos, val);
  101.     up(id << 1 | 1, mid + 1, r, pos, val);
  102.     st[id] = merge(st[id << 1], st[id << 1 | 1]);
  103. }
  104.  
  105. void build(int id, int l, int r) {
  106.     if(l == r) {
  107.         st[id].dp[1][1] = abs(d[l]);
  108.         st[id].tail = st[id].head = (d[l] >= 0 ? 1 : - 1);
  109.         return;
  110.     }
  111.     int mid = (l + r) / 2;
  112.     build(id << 1, l, mid);
  113.     build(id << 1 | 1, mid + 1, r);
  114.     st[id] = merge(st[id << 1], st[id << 1 | 1]);
  115. }
  116.  
  117. Node get(int id, int l, int r, int u, int v) {
  118.     if(l > v || r < u) return {0, 0, 0, 0, 0, 0};
  119.     if(l >= u && r <= v) return st[id];
  120.     int mid = (l + r) / 2;
  121.     return merge(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
  122. }
  123.  
  124. void solve() {
  125.     FOR(i, 1, n - 1) up(1, 1, n - 1, i, 0);
  126.     while(q--) {
  127.         int l, r, x; cin >> l >> r >> x;
  128.         up(1, 1, n - 1, l - 1, x);
  129.         up(1, 1, n - 1, r, - x);
  130.         cout << st[1].dp[1][1] << "\n";
  131.     }
  132. }
  133.  
  134. int32_t main() {
  135.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);srand(time(0));
  136.     if (fopen(Roxy".inp","r")) {
  137.         freopen(Roxy".inp","r",stdin);
  138.         freopen(Roxy".out","w",stdout);
  139.     }
  140.     if (mtt) cin>> test;
  141.     FOR (i, 1, test) {
  142.         init();
  143.         solve();
  144.     }
  145.     cerr<<el<<"TIME : " << 0.001*clock() <<"s"<<el;
  146. }
Success #stdin #stdout #stderr 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
TIME : 5.48s
https://ideone.com/9n4B1c
language:
C++14 (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!