제출 #1136064

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136064		duckindog	Progression (NOI20_progression)	C++17	24 / 100	3098 ms	57260 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];

const int null = -1'000'000'000'000;
namespace IT1 { 
  int f[N << 2], asnLazy[N << 2], addLazy[N << 2];

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

      asnLazy[s] = null;
    }
    if (addLazy[s]) { 
      f[s << 1] += (mid - l + 1) * addLazy[s];
      f[s << 1 | 1] += (r - mid) * addLazy[s];
      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] += (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] = f[s << 1] + f[s << 1 | 1];
  }
  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;
      asnLazy[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] = f[s << 1] + f[s << 1 | 1];
  }
  int query(int s, int l, int r, int u, int v) { 
    if (v < l || u > r) return 0;
    if (u <= l && r <= v) return f[s];
    push(s, l, r);
    int mid = (l + r) >> 1;
    return query(s << 1, l, mid, u, v) + query(s << 1 | 1, mid + 1, r, u, v);
  }
  
  inline void update(int l, int r, int x) { 
    update(1, 1, n, l, r, x);
  }
  inline void assign(int l, int r, int x) { 
    assign(1, 1, n, l, r, x);
  }
  inline int query(int p) { 
    return query(1, 1, n, 1, p);
  }
};

namespace IT2 { 
  struct Node { 
    int pref, suff, best;
    Node() : pref(0), suff(0), best(0) {}
    Node(int x) : pref(x), suff(x), best(x) {}
  };
  Node f[N << 2];
  bool lazy[N << 2];

  inline int value(int p) { 
    return IT1::query(p) - IT1::query(p - 1);
  }

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

    return ret;
  }

  void push(int s, int l, int r) { 
    if (!lazy[s]) return;
    int mid = (l + r) >> 1;
    f[s << 1] = mid - l + 1;  f[s << 1 | 1] = r - mid;
    lazy[s << 1] |= lazy[s];  lazy[s << 1 | 1] |= lazy[s];
    lazy[s] = false;
  }
  void update(int s, int l, int r, int u, int v) { 
    if (v < l || u > r) return;
    if (u <= l && r <= v) { 
      f[s] = r - l + 1;
      lazy[s] = true;
      return;
    }
    push(s, l, r);
    int mid = (l + r) >> 1;
    update(s << 1, l, mid, u, v);  update(s << 1 | 1, mid + 1, r, u, v);
    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);
  }

  inline void update(int l, int r) { 
    update(1, 2, n, l, r);
  }
}

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

  cin >> n >> q;
  for (int i = 1; i <= n; ++i) cin >> d[i];
  
  for (int i = 1; i <= n; ++i) { 
    IT1::update(1, 1, n, i, i, d[i]);
    IT1::update(1, 1, n, i + 1, i + 1, -d[i]);
  }
  for (int i = 2; i <= n; ++i)
    IT2::update(1, 2, n, i, i);
  
  while (q--) {
    int type; cin >> type;
    if (type == 1) { 
      int l, r, s, c; cin >> l >> r >> s >> c;
      { // IT1
        IT1::update(l + 1, r, c);
        IT1::update(r + 1, r + 1, -(r - l) * c);
        IT1::update(l, l, s);
        IT1::update(r + 1, r + 1, -s);
      }
      { // IT2
        IT2::update(l, l);
        IT2::update(r + 1, r + 1);
      }
    } else if (type == 2) { 
      int l, r, s, c; cin >> l >> r >> s >> c;
      { // IT1
        int save = IT1::query(r + 1);
        IT1::update(l, l, -IT1::query(l));
        IT1::assign(l + 1, r, c);
        IT1::update(r + 1, r + 1, -(r - l) * c);
        IT1::update(l, l, s);
        IT1::update(r + 1, r + 1, -s);
        IT1::update(r + 1, r + 1, save - IT1::query(r + 1));
      }
      { // IT2
        IT2::update(l, l);
        IT2::update(l + 1, r);
        IT2::update(r + 1, r + 1);
      }
    } else { 
      int l, r; cin >> l >> r;
      cout << (l == r ? 1 : IT2::query(1, 2, n, l + 1, r).best + 1) << "\n";
    }
  }
}

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