Submission #1245792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245792		Zero_OP	Progression (NOI20_progression)	C++20	100 / 100	967 ms	115944 KiB

Progression

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r) - 1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define sum_of(v) accumulate(all(v), 0ll)
#define compact(v) v.erase(unique(all(v)), end(v))

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;

using vi = vector<int>;
using vb = vector<bool>;
using vc = vector<char>;
using vl = vector<ll>;
using vd = vector<db>;

using vpi = vector<pi>;
using vpl = vector<pl>;

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif // LOCAL
}

const int MAX = 3e5 + 5;

struct Node{
      ll prefix_diff, suffix_diff;
      int prefix, suffix, best; bool same;

      Node() : prefix_diff(), suffix_diff(), prefix(), suffix(), best(), same() {}
      Node(ll v) : prefix_diff(v), suffix_diff(v), prefix(1), suffix(1), best(1), same(true) {}

      friend Node operator + (const Node& a, const Node& b){
            Node c;
            c.prefix_diff = a.prefix_diff;
            c.suffix_diff = b.suffix_diff;
            c.prefix = a.prefix;
            c.suffix = b.suffix;
            c.same = a.same & b.same & (a.suffix_diff == b.prefix_diff);
            if(a.same && a.suffix_diff == b.prefix_diff) c.prefix = a.prefix + b.prefix;
            if(b.same && a.suffix_diff == b.prefix_diff) c.suffix = a.suffix + b.prefix;
            c.best = max(a.best, b.best);
            if(a.suffix_diff == b.prefix_diff) maximize(c.best, a.suffix + b.prefix);
            return c;
      }

      void debug(){
            cout << dbg(prefix_diff) << dbg(prefix) << '\n';
            cout << dbg(suffix_diff) << dbg(suffix) << '\n';
            cout << dbg(best) << dbg(same) << '\n';
      }
} st[MAX << 2];

struct Line{
      ll a, b;
      Line() : a(0), b(0) {}
      Line(ll a, ll b) : a(a), b(b) {}
      ll operator () (ll x) const { return a * x + b; }

      Line& operator += (const Line& o){
            a += o.a;
            b += o.b;
            return *this;
      }
};

struct LichaoSegmentTree{
      vector<Line> st;
      vb done;

      LichaoSegmentTree(int n) : st(n << 2, Line(0, 0)), done(n << 2, false) {}

      void apply_add(int id, const Line& d){
            st[id] += d;
      }

      void apply_set(int id, const Line& d){
            st[id] = d;
            done[id] = true;
      }

      void push_down(int id){
            if(done[id]){
                  apply_set(id << 1, st[id]);
                  apply_set(id << 1 | 1, st[id]);
                  done[id] = false;
                  st[id].a = 0; st[id].b = 0;
            }

            if(st[id].a != 0 || st[id].b != 0){
                  apply_add(id << 1, st[id]);
                  apply_add(id << 1 | 1, st[id]);
                  st[id].a = 0; st[id].b = 0;
            }
      }

      void increase(int id, int l, int r, int u, int v, Line d){
            if(u <= l && r <= v) apply_add(id, d);
            else{
                  int mid = l + r >> 1;
                  push_down(id);
                  if(u <= mid) increase(id << 1, l, mid, u, v, d);
                  if(mid < v)  increase(id << 1 | 1, mid + 1, r, u, v, d);
            }
      }

      void set_value(int id, int l, int r, int u, int v, Line d){
            if(u <= l && r <= v) apply_set(id, d);
            else{
                  int mid = l + r >> 1;
                  push_down(id);
                  if(u <= mid) set_value(id << 1, l, mid, u, v, d);
                  if(mid < v)  set_value(id << 1 | 1, mid + 1, r, u, v, d);
            }
      }

      ll query(int id, int l, int r, int pos){
            if(l == r) return st[id](pos);
            int mid = l + r >> 1;
            push_down(id);
            if(pos <= mid) return query(id << 1, l, mid, pos);
            else return query(id << 1 | 1, mid + 1, r, pos);
      }

      void debug(int id, int l, int r){
            if(l == r) cout << st[id](l) << ' ';
            else{
                  int mid = l + r >> 1;
                  push_down(id);
                  debug(id << 1, l, mid);
                  debug(id << 1 | 1, mid + 1, r);
            }
      }
};

const int inf = 1e9 + 9;
struct SegmentTreeSubarray{
      vector<Node> st;
      vl lazy_add, lazy_set;

      SegmentTreeSubarray(int n) : st(n << 2), lazy_add(n << 2, 0), lazy_set(n << 2, inf) {}

      void apply_add(int id, ll d){
            st[id].prefix_diff += d;
            st[id].suffix_diff += d;
            lazy_add[id] += d;
      }

      void apply_set(int id, int l, int r, int val){
            st[id].prefix = r - l + 1;
            st[id].suffix = r - l + 1;
            st[id].best = r - l + 1;
            st[id].prefix_diff = val;
            st[id].suffix_diff = val;
            lazy_set[id] = val;
            lazy_add[id] = 0;
            st[id].same = true;
      }

      void push_down(int id, int l, int r, int mid){
            if(lazy_set[id] != inf){
                  apply_set(id << 1, l, mid, lazy_set[id]);
                  apply_set(id << 1 | 1, mid + 1, r, lazy_set[id]);
                  lazy_set[id] = inf;
            }

            if(lazy_add[id] != 0){
                  apply_add(id << 1, lazy_add[id]);
                  apply_add(id << 1 | 1, lazy_add[id]);
                  lazy_add[id] = 0;
            }
      }

      void increase(int id, int l, int r, int u, int v, ll d){
            if(u <= l && r <= v) apply_add(id, d);
            else{
                  int mid = l + r >> 1;
                  push_down(id, l, r, mid);
                  if(u <= mid) increase(id << 1, l, mid, u, v, d);
                  if(mid < v)  increase(id << 1 | 1, mid + 1, r, u, v, d);
                  st[id] = st[id << 1] + st[id << 1 | 1];
            }
      }

      void set_value(int id, int l, int r, int u, int v, ll val){
            if(u <= l && r <= v) apply_set(id, l, r, val);
            else{
                  int mid = l + r >> 1;
                  push_down(id, l, r, mid);
                  if(u <= mid) set_value(id << 1, l, mid, u, v, val);
                  if(mid < v)  set_value(id << 1 | 1, mid + 1, r, u, v, val);
                  st[id] = st[id << 1] + st[id << 1 | 1];
            }
      }

      Node query(int id, int l, int r, int u, int v){
            if(u <= l && r <= v) {
//                  cout << dbg(l) << dbg(r) << '\n';
                  return st[id];
            }
            int mid = l + r >> 1;
            push_down(id, l, r, mid);
            if(u > mid) return query(id << 1 | 1, mid + 1, r, u, v);
            if(mid >= v) return query(id << 1, l, mid, u, v);
            return query(id << 1, l, mid, u, v) + query(id << 1 | 1, mid + 1, r, u, v);
      }

      void debug(int id, int l, int r){
            if(l == r) cout << st[id].prefix_diff << ' ';
            else{
                  int mid = l + r >> 1;
                  push_down(id, l, r, mid);
                  debug(id << 1, l, mid);
                  debug(id << 1 | 1, mid + 1, r);
            }
      }
};

signed main(){
      setIO();

      int N, Q;
      cin >> N >> Q;

      vi D(N);
      FOR(i, 0, N) cin >> D[i];

      LichaoSegmentTree lct(N);
      SegmentTreeSubarray tr(N-1);

      FOR(i, 0, N) lct.set_value(1, 0, N-1, i, i, Line(0, D[i]));
      FOR(i, 0, N-1) tr.set_value(1, 0, N-2, i, i, D[i+1] - D[i]);

      function<void(int)> fix = [&](int x){
            assert(0 <= x && x < N-1);
            ll prev = lct.query(1, 0, N-1, x);
            ll next = lct.query(1, 0, N-1, x+1);
            tr.set_value(1, 0, N-2, x, x, next - prev);
      };

      while(Q--){
            int T;
            cin >> T;

            if(T == 1){
                  int L, R, S, C;
                  cin >> L >> R >> S >> C;

                  --L, --R;

                  lct.increase(1, 0, N-1, L, R, Line(C, S - 1LL * L * C));
                  if(L<R) tr.increase(1, 0, N-2, L, R-1, C);

                  if(L>0) fix(L-1);
                  if(R<N-1) fix(R);
            } else if(T == 2){
                  int L, R, S, C;
                  cin >> L >> R >> S >> C;

                  --L, --R;
                  lct.set_value(1, 0, N-1, L, R, Line(C, S - 1LL * L * C));
                  if(L<R) tr.set_value(1, 0, N-2, L, R-1, C);

                  if(L>0) fix(L-1);
                  if(R<N-1) fix(R);
            } else{
                  int L, R;
                  cin >> L >> R;

                  --L, --R;

//                  cout << L << ' ' << R << '\n';

                  if(L == R) cout << 1 << '\n';
                  else cout << tr.query(1, 0, N-2, L, R-1).best + 1 << '\n';
            }
      }

      return 0;
}

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