제출 #1136240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136240		duckindog	Progression (NOI20_progression)	C++17	100 / 100	736 ms	76656 KiB

Progression

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 300'000 + 10;
int n, q;
int d[N];

namespace IT { 
  static const int null = 1'000'000'000'000;
  struct Node { 
    int pref, suff, best;
    int valuePref, valueSuff;
    int sum;
    Node() : pref(0), suff(0), best(0), 
              valuePref(null), valueSuff(null),
              sum(0) {}
    Node(int length, int value, int sum) : pref(length), suff(length), best(length), 
                                            valuePref(value), valueSuff(value),
                                            sum(sum) {}

    Node& operator += (int add) { 
      valuePref += add, valueSuff += add;
      return *this;
    }
  };
  Node f[N << 2];
  int agnLazy[N << 2], addLazy[N << 2];

  Node merge(const Node& lt, const Node& rt, int l, int r) { 
    Node ret;
    
    ret.pref = lt.pref, ret.valuePref = lt.valuePref;
    ret.suff = rt.suff, ret.valueSuff = rt.valueSuff;
    ret.best = max(lt.best, rt.best);
    if (lt.valueSuff == rt.valuePref) { 
      ret.best = max(ret.best, lt.suff + rt.pref);
      
      int mid = (l + r) >> 1;
      if (lt.pref == mid - l + 1) ret.pref += rt.pref;
      if (rt.suff == r - mid) ret.suff += lt.suff;
    }
    ret.sum = lt.sum + rt.sum;

    return ret;
  }

  void build(int s, int l, int r) { 
    agnLazy[s] = null;
    if (l == r) { 
      f[s].pref = f[s].suff = f[s].best = 1;
      f[s].valuePref = f[s].valueSuff = d[l] - d[l - 1];
      f[s].sum = d[l] - d[l - 1];
      return;
    }
    int mid = (l + r) >> 1;
    build(s << 1, l, mid); build(s << 1 | 1, mid + 1, r);
    f[s] = merge(f[s << 1], f[s << 1 | 1], l, r);
  }

  void push(int s, int l, int r) { 
    int mid = (l + r) >> 1;
    if (agnLazy[s] != null) { 
      f[s << 1] = {mid - l + 1, agnLazy[s], (mid - l + 1) * agnLazy[s]};  
      f[s << 1 | 1] = {r - mid, agnLazy[s], (r - mid) * agnLazy[s]};
      
      agnLazy[s << 1] = agnLazy[s << 1 | 1] = agnLazy[s];
      addLazy[s << 1] = addLazy[s << 1 | 1] = 0;
      
      agnLazy[s] = null;
    }
    if (addLazy[s]) { 
      f[s << 1] += addLazy[s];
      f[s << 1 | 1] += addLazy[s];

      f[s << 1].sum += addLazy[s] * (mid - l + 1);
      f[s << 1 | 1].sum += addLazy[s] * (r - mid);

      addLazy[s << 1] += addLazy[s];
      addLazy[s << 1 | 1] += addLazy[s];

      addLazy[s] = 0;
    }
  }
  void update(int s, int l, int r, int u, int v, int x) { 
    if (v < l || u > r) return;
    if (u <= l && r <= v) { 
      f[s] += x;
      f[s].sum += (r - l + 1) * x;
      addLazy[s] += x;
      return;
    }
    push(s, l, r);
    int mid = (l + r) >> 1;
    update(s << 1, l, mid, u, v, x); update(s << 1 | 1, mid + 1, r, u, v, x);
    f[s] = merge(f[s << 1], f[s << 1 | 1], l, r);
  }
  void assign(int s, int l, int r, int u, int v, int x) { 
    if (v < l || u > r) return;
    if (u <= l && r <= v) { 
      f[s] = {r - l + 1, x, (r - l + 1) * x};
      agnLazy[s] = x;
      addLazy[s] = 0;
      return;
    }
    push(s, l, r);
    int mid = (l + r) >> 1;
    assign(s << 1, l, mid, u, v, x); assign(s << 1 | 1, mid + 1, r, u, v, x);
    f[s] = merge(f[s << 1], f[s << 1 | 1], l, r);
  }
  Node query(int s, int l, int r, int u, int v) { 
    if (v < l || u > r) return Node();
    if (u <= l && r <= v) return f[s];
    push(s, l, r);
    int mid = (l + r) >> 1;
    return merge(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v), l, r);
  }

  void update(int u, int v, int x) { 
    update(1, 1, n, u, v, x);
  }
  void assign(int u, int v, int x) { 
    assign(1, 1, n, u, v, x);
  }
  Node query(int u, int v) { 
    return query(1, 1, n, u, v);
  }
  int value(int p) { 
    return query(1, 1, n, 1, p).sum;
  }
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> q;
  for (int i = 1; i <= n; ++i) cin >> d[i];

  IT::build(1, 1, n);
  while (q--) { 
    int type; cin >> type;

    if (type == 1) { 
      int l, r, s, c; cin >> l >> r >> s >> c;
      IT::update(l, l, s);
      IT::update(l + 1, r, c);
      IT::update(r + 1, r + 1, -s - (r - l) * c);
    } else if (type == 2) { 
      int l, r, s, c; cin >> l >> r >> s >> c;
      int save = IT::value(r + 1);
      IT::assign(l, l, s - IT::value(l - 1));
      IT::assign(l + 1, r, c);
      IT::assign(r + 1, r + 1, save - IT::value(r));
    } else { 
      int l, r; cin >> l >> r;
      cout << (l == r ? 1 : IT::query(l + 1, r).best + 1) << "\n";
    }
  }
}

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