Submission #1209866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209866		loom	Progression (NOI20_progression)	C++20	44 / 100	645 ms	119408 KiB

Progression

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 5e18
#define nl '\n'

struct node{
   int ta, la, ra, lv, rv;
   int st = inf, ad = 0;
};

const int N = 3e5+1;
node seg[4*N];
int a[N];

void lazy(int l, int r, int p){
   auto &s = seg[p];

   int v = s.st;
   if(v != inf){
      s.st = inf;
      s.ta = s.la = s.ra = r-l+1;
      s.lv = s.rv = v;

      if(l != r){
         seg[p*2].st = seg[p*2+1].st = v;
         seg[p*2].ad = seg[p*2+1].ad = 0;
      }
   }

   v = s.ad;
   if(v != 0){
      s.ad = 0;
      s.lv += v;
      s.rv += v;

      if(l != r){
         seg[p*2].ad += v;
         seg[p*2+1].ad += v;
      }
   }
}

node unite(int xln, node x, int yln, node y){
   node s;
   s.ta = max(x.ta, y.ta);
   if(x.rv == y.lv) s.ta = max(s.ta, x.ra + y.la);

   s.la = x.la;
   if(x.la == xln and x.rv == y.lv) s.la += y.la; 

   s.ra = y.ra;
   if(y.ra == yln and y.lv == x.rv) s.ra += x.ra; 

   s.lv = x.lv;
   s.rv = y.rv;
   return s;
}

void build(int l, int r, int p){
   if(l == r){
      seg[p].ta = seg[p].la = seg[p].ra = 1;
      seg[p].lv = seg[p].rv = a[l];
      return;
   }

   int m = (l+r)/2;
   build(l, m, p*2);
   build(m+1, r, p*2+1);
   seg[p] = unite(m-l+1, seg[p*2], r-m, seg[p*2+1]);
}

void upd(int l, int r, int p, int w, int ql, int qr, int v){
   lazy(l, r, p);

   if(r < ql or qr < l) return;
   if(ql <= l and r <= qr){
      if(w){
         seg[p].st = v;
         seg[p].ad = 0;
      }
      else seg[p].ad += v;

      lazy(l, r, p);
      return;
   }

   int m = (l+r)/2;
   upd(l, m, p*2, w, ql, qr, v);
   upd(m+1, r, p*2+1, w, ql, qr, v);
   seg[p] = unite(m-l+1, seg[p*2], r-m, seg[p*2+1]);
}

node qry(int l, int r, int p, int ql, int qr){
   lazy(l, r, p);

   if(r < ql or qr < l) return {};
   if(ql <= l and r <= qr) return seg[p];

   int m = (l+r)/2;
   node x = qry(l, m, p*2, ql, qr);
   node y = qry(m+1, r, p*2+1, ql, qr);

   if(qr <= m) return x;
   if(ql > m) return y;
   return unite(m - max(l, ql) + 1, x, min(r, qr) - m, y);
}

void upd(int w, int ql, int qr, int v){
   upd(2, N-1, 1, w, ql, qr, v);
}

node qry(int ql, int qr){
   return qry(2, N-1, 1, ql, qr);
}

struct node2{
   int vl, sts = inf, stc, ads = 0, adc = 0;
};

node2 seg2[4*N];
int b[N];

void lazy2(int l, int r, int p){
   auto &s = seg2[p];
   int m = (l+r)/2;

   if(s.sts != inf){
      if(l == r) s.vl = s.sts;

      if(l != r){
         auto &x = seg2[p*2], &y = seg2[p*2+1];

         x.sts = s.sts;
         y.sts = s.sts + (m+1-l) * s.stc;
         x.stc = y.stc = s.stc;
         x.ads = x.adc = y.ads = y.adc = 0;
      }
      s.sts = inf;
   }

   if(s.ads != 0 or s.adc != 0){
      if(l == r) s.vl += s.ads;

      if(l != r){
         auto &x = seg2[p*2], &y = seg2[p*2+1];

         x.ads += s.ads;
         y.ads += s.ads + (m+1-l) * s.adc;
         x.adc += s.adc;
         y.adc += s.adc;
      }
      s.ads = s.adc = 0;
   }
}

void build2(int l, int r, int p){
   if(l == r){
      seg2[p].vl = b[l];
      return;
   }

   int m = (l+r)/2;
   build2(l, m, p*2);
   build2(m+1, r, p*2+1);
}

void upd2(int l, int r, int p, int w, int ql, int qr, int s, int c){
   lazy2(l, r, p);

   if(r < ql or qr < l) return;
   if(ql <= l and r <= qr){
      if(w){
         seg2[p].sts = s + (l-ql)*c;
         seg2[p].stc = c;
         seg2[p].ads = seg2[p].adc = 0;
      }
      else{
         seg2[p].ads += s + (l-ql)*c;
         seg2[p].adc += c;
      }

      lazy2(l, r, p);
      return;
   }

   int m = (l+r)/2;
   upd2(l, m, p*2, w, ql, qr, s, c);
   upd2(m+1, r, p*2+1, w, ql, qr, s, c);
}

int qry2(int l, int r, int p, int q){
   lazy2(l, r, p);

   if(l == r) return seg2[p].vl;

   int m = (l+r)/2;
   if(q <= m) return qry2(l, m, p*2, q);
   else return qry2(m+1, r, p*2+1, q);
}

void upd2(int w, int ql, int qr, int s, int c){
   upd2(1, N-1, 1, w, ql, qr, s, c);
}

int qry2(int q){
   return qry2(1, N-1, 1, q);
}

inline void solve(){
   int n, q;
   cin>>n>>q;
   for(int i=1; i<=n; i++){
      cin>>b[i]; 
      a[i] = b[i] - b[i-1];
   }

   build(2, N-1, 1);
   build2(1, N-1, 1);

   while(q--){
      int w;
      cin>>w;

      if(w == 1){
         int l, r, s, c;
         cin>>l>>r>>s>>c;

         if(l > 2) upd(0, l, l, s);
         if(l+1 <= r) upd(0, l+1, r, c);
         if(r < n) upd(0, r+1, r+1, -s - (r-l)*c);

         upd2(0, l, r, s, c);
      }
      else if(w == 2){
         int l, r, s, c;
         cin>>l>>r>>s>>c;

         if(l > 2){
            int pv = qry2(l-1);
            upd(1, l, l, s - pv);
         }
         if(l+1 <= r) upd(1, l+1, r, c);
         if(r < n){
            int nv = qry2(r+1);
            upd(1, r+1, r+1, nv - s - (r-l)*c);
         }

         upd2(1, l, r, s, c);
      }
      else{
         int l, r;
         cin>>l>>r;

         cout<<(l == r ? 1 : qry(l+1, r).ta + 1)<<nl;
      }
   }
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 15
• Subtask 3: 35 / 35
• Subtask 4: 0 / 11
• Subtask 5: 0 / 13
• Subtask 6: 0 / 17