fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1e5 + 7;
  4. int n,m,a[N];
  5. struct node
  6. {
  7.     int leftVal,rightVal;
  8.     int incLeft, incRight;
  9.     int fluctLeft, fluctRight;
  10.     int len,best;
  11. } st[4*N];
  12. node Merge(node a, node b)
  13. {
  14.     int Best = max(a.best,b.best);
  15.     // update inc subse
  16.  //   cout << "GG " << b.incLeft << ' ' <<  b.fluctLeft << ' ' << a.fluctLeft << endl;
  17.     int incR = b.incRight, incL = a.incLeft;
  18.     if(a.rightVal < b.leftVal && b.incRight == b.len) {
  19.         incR = a.incRight + b.len;
  20.     }
  21.     if(a.rightVal > b.leftVal && a.incLeft == a.len) {
  22.         incL = b.incLeft + a.len;
  23.     }
  24.     // update best
  25.     // case 1 converge
  26.     if(a.rightVal > b.leftVal || a.rightVal < b.leftVal)
  27.     {
  28.         Best = max(Best,a.incRight+b.incLeft);
  29.     }
  30.     // case2 continue
  31.     int fluctL = max(a.fluctLeft,a.incLeft), fluctR = (b.fluctRight,b.incRight);
  32.     if(a.rightVal > b.leftVal || a.rightVal < b.leftVal)
  33.     {
  34.         if(b.len == b.incLeft) fluctR = max(fluctR,a.incRight + b.incLeft);
  35.         if(a.len == a.incRight) fluctL = max(fluctL,a.incRight + b.incLeft);
  36.         if(a.len == a.fluctLeft && a.rightVal > b.leftVal) fluctL = max(fluctL,a.fluctLeft + b.incLeft);
  37.         if(b.len == b.fluctRight && a.rightVal < b.leftVal) fluctR = max(fluctL,b.fluctRight + a.incRight);
  38.     }
  39.     if(a.fluctRight != 0 && a.rightVal > b.leftVal) {
  40.             Best = max(Best,a.fluctRight+b.incLeft);
  41.             if(b.incLeft == b.len) fluctR = max(fluctR,a.fluctRight+b.incLeft);
  42.     }
  43.     if(b.fluctLeft != 0 && a.rightVal < b.leftVal) {
  44.         Best = max(Best,b.fluctLeft+a.incRight);
  45.         if(a.incRight == a.len) fluctL = max(fluctL,b.fluctLeft+a.incRight);
  46.     }
  47.     Best = max({Best,fluctR,fluctL});
  48.     //
  49.     return {a.leftVal,b.rightVal,
  50.             incL,incR,
  51.             fluctL,fluctR,
  52.             a.len+b.len,Best};
  53. }
  54. void build(int id, int l, int r)
  55. {
  56.     if(l > r) return;
  57.     if(l == r){
  58.         st[id] = {a[l],a[l],1,1,0,0,1,0};
  59.         return;
  60.     }
  61.     int mid = (l+r)/2;
  62.     build(2*id,l,mid);
  63.     build(2*id+1,mid+1,r);
  64.     st[id] = Merge(st[2*id],st[2*id+1]);
  65.  
  66. }
  67. void update(int id, int l, int r, int u)
  68. {
  69.     if(l > u || r < u) return;
  70.     if(l == r)
  71.     {
  72.         st[id] = {a[l],a[l],1,1,0,0,1,0};
  73.         return;
  74.     }
  75.     int mid = (l+r)/2;
  76.     update(2*id,l,mid,u);
  77.     update(2*id+1,mid+1,r,u);
  78.     st[id] = Merge(st[2*id],st[2*id+1]);
  79. }
  80. int main()
  81. {
  82.     ios_base::sync_with_stdio(0);
  83.     cin.tie(0);cout.tie(0);
  84.     cin >> n >> m;
  85.     for(int i = 1; i <= n; i++) cin >> a[i];
  86.     build(1,1,n);
  87.   //  cout << st[1].best << endl;
  88.     for(int i = 1; i <= m; i++)
  89.     {
  90.         int x,y; cin >> x >> y;
  91.         a[x] = y;
  92.         update(1,1,n,x);
  93.         cout << st[1].best <<'\n';
  94.     }
  95. }
  96.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dWRw7A
language:
C++14 (gcc 8.3)
created:
7 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!