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 " << a.incRight << ' ' <<  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.     }
  37.    // cout << a.fluctRight << endl;
  38.    // cout << a.rightVal <<' ' << b.leftVal << endl;
  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.          //   cout << a.fluctRight <<' ' << b.incLeft << endl;
  43.     }
  44.     if(b.fluctLeft != 0 && a.rightVal < b.leftVal) {
  45.         Best = max(Best,b.fluctLeft+a.incRight);
  46.         if(a.incRight == a.len) fluctL = max(fluctL,b.fluctLeft+a.incRight);
  47.     }
  48.  
  49.     //
  50.     return {a.leftVal,b.rightVal,
  51.             incL,incR,
  52.             fluctL,fluctR,
  53.             a.len+b.len,Best};
  54. }
  55. void build(int id, int l, int r)
  56. {
  57.     if(l > r) return;
  58.     if(l == r){
  59.         st[id] = {a[l],a[l],1,1,0,0,1,0};
  60.         return;
  61.     }
  62.     int mid = (l+r)/2;
  63.     build(2*id,l,mid);
  64.     build(2*id+1,mid+1,r);
  65.     cout << l <<' ' << mid << ' ' << r << endl;
  66.     st[id] = Merge(st[2*id],st[2*id+1]);
  67.  
  68. }
  69. void update(int id, int l, int r, int u)
  70. {
  71.     if(l > u || r < u) return;
  72.     if(l == r)
  73.     {
  74.         st[id] = {a[l],a[l],1,1,0,0,1,0};
  75.         return;
  76.     }
  77.     int mid = (l+r)/2;
  78.     update(2*id,l,mid,u);
  79.     update(2*id+1,mid+1,r,u);
  80.         cout << l <<' ' <<r  <<' ' << mid << endl;
  81.     st[id] = Merge(st[2*id],st[2*id+1]);
  82.     // cout << l <<' ' << r << ' ' << st[id].fluctRight << ' ' << st[id].fluctLeft <<' ' << st[id].best << endl;
  83. }
  84. int main()
  85. {
  86.     ios_base::sync_with_stdio(0);
  87.     cin.tie(0);cout.tie(0);
  88.     cin >> n >> m;
  89.     for(int i = 1; i <= n; i++) cin >> a[i];
  90.     build(1,1,n);
  91.     for(int i = 1; i <= m; i++)
  92.     {
  93.         int x,y; cin >> x >> y;
  94.         a[x] = y;
  95.         update(1,1,n,x);
  96.         cout << st[1].best <<'\n';
  97.     }
  98. }
  99.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8RYyt7
language:
C++14 (gcc 8.3)
created:
2 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!