Submission #3609601


Source Code Expand

// includes {{{
#include <algorithm>
#include <cassert>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
// }}}
// #include<bits/stdc++.h>
using namespace std;
using ll = long long;

/// --- RedBlackTree Sequence Library {{{ ///

// my_shared_ptr {{{

template < class T >
class my_shared_ptr {
private:
  size_t *counter;
  T *ptr;

public:
  operator bool() { return bool(counter); }
  my_shared_ptr() : counter(0) {}
  my_shared_ptr(T *ptr) : ptr(ptr) {
    if(ptr) counter = new size_t(1);
  }
  ~my_shared_ptr() { reset(); }
  my_shared_ptr(const my_shared_ptr &sptr) { *this = sptr; }
  my_shared_ptr(my_shared_ptr &&sptr) { *this = move(sptr); }
  my_shared_ptr &operator=(const my_shared_ptr &sptr) {
    counter = sptr.counter;
    ptr = sptr.ptr;
    if(counter) ++*counter;
    return *this;
  }
  my_shared_ptr &operator=(my_shared_ptr &&sptr) {
    counter = sptr.counter;
    ptr = sptr.ptr;
    sptr.counter = 0;
    sptr.ptr = 0; // explicit
    return *this;
  }
  T *release() {
    delete counter;
    counter = 0;
    T *r = ptr;
    ptr = 0; // explicit
    return r;
  }
  T *get() { return counter ? ptr : 0; }
  void reset() {
    if(counter) {
      if(--*counter == 0) {
        delete counter;
        delete ptr;
      }
      counter = 0;
      ptr = 0; // explicit
    }
  }
  int use_count() { return use_count ? *counter : 0; }
  T &operator*() const noexcept { return *ptr; }
  T *operator->() const noexcept { return ptr; }
};

// }}}

#include <algorithm>
#include <utility>
// #include <memory>

template < class Monoid, class M_act, bool isPersistent >
struct RedBlackTreeSequenceBase {
private:
  using Node = RedBlackTreeSequenceBase;
  using ptr = my_shared_ptr< Node >;

private:
  ptr c[2];
  using X = typename Monoid::T;
  using M = typename M_act::M;
  X val = Monoid::identity();
  X accum = Monoid::identity();
  M lazy = M_act::identity();
  bool rev = false;
  int sz;

public:
  enum Color { BLACK, RED };
  bool color;
  unsigned char level;

public:
  // leaf node
  RedBlackTreeSequenceBase(X val = Monoid::identity())
      : val(val), accum(val), sz(1), color(BLACK), level(0) {}

private:
  // internal node
  RedBlackTreeSequenceBase(Node *l, Node *r, Color color)
      : c({ptr(l), ptr(r)}), color(color) {
    prop(this);
  }

  // prop and eval {{{

private:
  // [RBT] a is internal node
  // a is evaled
  // a->c[0], c[1] is proped, evaled
  friend Node *prop(Node *a) {
    a->sz = a->c[0]->sz + a->c[1]->sz;
    a->accum = Monoid::op(a->c[0]->accum, a->c[1]->accum);
    a->level = max(a->c[0]->level + (a->c[0]->color == BLACK),
                   a->c[1]->level + (a->c[1]->color == BLACK));
    return a;
  }
  // call before use val, accum
  friend Node *eval(Node *a) {
    if(a->lazy != M_act::identity()) {
      a->val = M_act::actInto(a->lazy, -1, 1, a->val);
      a->accum = M_act::actInto(a->lazy, -1, a->sz, a->accum);
      for(int i = 0; i < 2; i++)
        if(a->c[i]) {
          a->c[i] = ptr(clone(a->c[i]));
          a->c[i]->lazy = M_act::op(a->lazy, a->c[i]->lazy);
        }
      a->lazy = M_act::identity();
    }
    if(a->rev) {
      swap(a->c[0], a->c[1]);
      for(int i = 0; i < 2; i++)
        if(a->c[i]) {
          a->c[i] = ptr(clone(a->c[i]));
          a->c[i]->rev ^= 1;
        }
      a->rev = false;
    }
    return a;
  }

  // }}}

  // BST Sequence functions {{{
public:
  friend void push_front(Node *&a, const X &x) { a = merge(new Node(x), a); }
  friend void push_back(Node *&a, const X &x) { a = merge(a, new Node(x)); }
  friend void insert(Node *&a, int k, const X &x) {
    Node *sl, *sr;
    tie(sl, sr) = split(a, k);
    a = merge(sl, merge(new Node(x), sr));
  }
  friend void insert(Node *&a, int k, Node *b) {
    Node *sl, *sr;
    tie(sl, sr) = split(a, k);
    a = merge(sl, merge(b, sr));
  }
  friend X pop_front(Node *&a) {
    Node *sl, *sr;
    tie(sl, sr) = split(a, 1);
    a = sr;
    X x = getValue(sl);
    delete sl;
    return x;
  }
  friend X pop_back(Node *&a) {
    Node *sl, *sr;
    tie(sl, sr) = split(a, size(a) - 1);
    a = sl;
    X x = getValue(sr);
    delete sr;
    return x;
  }
  friend X erase(Node *&a, int k) {
    Node *t = slice(a, k);
    X x = getValue(t);
    delete t;
    return x;
  }
  friend void erase(Node *&a, int l, int r) {
    Node *t = mslice(a, l, r);
    delete t;
  }
  friend Node *mslice(Node *&a, int k) {
    Node *sl, *sr, *tl, *tr;
    tie(sl, sr) = split(a, k + 1);
    tie(tl, tr) = split(sl, k);
    a = merge(tl, sr);
    return tr;
  }
  friend Node *mslice(Node *&a, int l, int r) {
    Node *sl, *sr, *tl, *tr;
    tie(sl, sr) = split(a, r);
    tie(tl, tr) = split(sl, l);
    a = merge(tl, sr);
    return tr;
  }
  friend void set1(Node *&a, int k, const X &x) {
    Node *sl, *sr, *tl, *tr;
    tie(sl, sr) = split(a, k + 1);
    tie(tl, tr) = split(sl, k);
    if(tr) tr->val = tr->accum = x;
    a = merge(merge(tl, tr), sr);
  }
  friend X getValue(Node *a) {
    return a ? (eval(a), a->val) : Monoid::identity();
  }
  friend X get(Node *&a, int k) {
    Node *sl, *sr, *tl, *tr;
    tie(sl, sr) = split(a, k + 1);
    tie(tl, tr) = split(sl, k);
    X res = tr ? tr->val : Monoid::identity();
    a = merge(merge(tl, tr), sr);
    return res;
  }
  friend void act(Node *&a, int l, int r, const M &m) {
    Node *sl, *sr, *tl, *tr;
    tie(sl, sr) = split(a, r);
    tie(tl, tr) = split(sl, l);
    if(tr) tr->lazy = M_act::op(m, tr->lazy);
    a = merge(merge(tl, tr), sr);
  }
  friend X query(Node *a) {
    return a ? (eval(a), a->accum) : Monoid::identity();
  }
  friend X query(Node *&a, int l, int r) {
    Node *sl, *sr, *tl, *tr;
    tie(sl, sr) = split(a, r);
    tie(tl, tr) = split(sl, l);
    X res = tr ? tr->accum : Monoid::identity();
    a = merge(merge(tl, tr), sr);
    return res;
  }
  friend void reverse(Node *a) {
    if(a) a->rev ^= 1;
  }
  friend void reverse(Node *&a, int l, int r) {
    Node *sl, *sr, *tl, *tr;
    tie(sl, sr) = split(a, r);
    tie(tl, tr) = split(sl, l);
    if(tr) tr->rev ^= 1;
    a = merge(merge(tl, tr), sr);
  }
  friend int size(Node *a) { return a ? a->sz : 0; }
  /// }}}--- ///

private:
  friend Node *clone(ptr &a) {
    if(isPersistent) {
      return &(*(new Node) = *a);
    } else {
      return a.release();
    }
  }

private:
  // [RBT]
  // a is evaled, NOT proped
  // a->c[_] is unique, evaled;
  // a->c[!R] is internal node
  // a->c[!R]->c[!R] is unique, evaled
  friend Node *rotate(Node *a, bool R) {
    Node *l = eval(a->c[!R].release());
    a->c[!R] = ptr(eval(clone(l->c[R])));
    l->c[R] = ptr(prop(a));
    return prop(l);
  }
  // [RBT]
  // a is evaled, NOT proped
  // a->[_] is unique, evaled
  // return proped, evaled
  friend Node *check(Node *a, bool R) {
    if(a->color == BLACK && a->c[!R]->color == RED &&
       a->c[!R]->c[!R]->color == RED) {
      a->color = RED;
      a->c[!R]->color = BLACK;
      if(a->c[R]->color == BLACK) return rotate(a, R);
      a->c[R] = ptr(clone(a->c[R]));
      a->c[R]->color = BLACK;
    }
    return prop(a);
  }
  // return proped, evaled
  friend Node *submerge(Node *a, Node *b) {
    if(a->level < b->level) {
      b = eval(b);
      b->c[0] = ptr(submerge(a, clone(b->c[0])));
      b->c[1] = ptr(eval(clone(b->c[1])));
      return check(b, 1);
    } else if(a->level > b->level) {
      a = eval(a);
      a->c[1] = ptr(submerge(clone(a->c[1]), b));
      a->c[0] = ptr(eval(clone(a->c[0])));
      return check(a, 0);
    } else {
      a = eval(a);
      b = eval(b);
      return new Node(a, b, RED);
    }
  }

public:
  // return evaled
  friend Node *merge(Node *a, Node *b) {
    if(!a) return b;
    if(!b) return a;
    Node *c = submerge(a, b);
    c->color = BLACK;
    return c;
  }
  // [0, k), [k, n)
  // return evaled
  friend pair< Node *, Node * > split(Node *a, int k) {
    if(!a) return {0, 0};
    a = eval(a);
    if(k == 0) return {0, a};
    if(k >= a->sz) return {a, 0};
    // a is internal
    Node *sl, *sr;
    Node *l = clone(a->c[0]), *r = clone(a->c[1]);
    delete a;
    if(k < l->sz) {
      tie(sl, sr) = split(l, k);
      return {sl, merge(sr, r)};
    }
    if(k > l->sz) {
      tie(sl, sr) = split(r, k - l->sz);
      return {merge(l, sl), sr};
    }
    return {eval(l), eval(r)};
  }
  friend Node *copy(Node *a) {
    assert(isPersistent);
    if(!a) return 0;
    return &(*(new Node) = *a);
  }
  friend Node *copy(Node *&a, int l, int r) {
    assert(isPersistent);
    if(!a) return 0;
    Node *sl, *sr, *tl, *tr;
    tie(sl, sr) = split(a, r);
    tie(tl, tr) = split(sl, l);
    Node *res = copy(tr);
    a = merge(merge(tl, tr), sr);
    return res;
  }
  template<class InputIter, class = typename iterator_traits<InputIter>::value_type>
  friend Node *build(Node *&a, InputIter first, InputIter last) {
    delete a;
    int n = distance(first, last);
    if(n == 0) return 0;
    vector<Node*> v(n), tmp(n);
    InputIter ite = first;
    for(int i = 0; i < n; ++i, ++ite) v[i] = new Node(*ite);
    while(v.size() != 1) {
      tmp.resize(v.size() >> 1);
      for(size_t i = 0; i < tmp.size(); i++) tmp[i] = merge(v[i << 1], v[(i << 1) | 1]);
      if(v.size() & 1) tmp.emplace_back(v.back());
      swap(v, tmp);
    }
    return a = v[0];
  }

  friend string to_string(Node *a) {
    if(!a) return "";
    return "(" + to_string(a->c[0].get()) + ", accum: " + to_string(a->accum) +
           " isBlack: " + to_string(a->color == BLACK) + ", " +
           to_string(a->c[1].get()) + ")";
  }
};

/// }}}--- ///

/// --- Monoid, M_act examples {{{ ///

/// --- Monoid examples {{{ ///

struct Nothing {
  using T = char;
  using M = char;
  static constexpr T op(const T &, const T &) { return 0; }
  static constexpr T identity() { return 0; }
  template < class X >
  static constexpr X actInto(const M &, ll, ll, const X &x) {
    return x;
  }
};

struct RangeMin {
  using T = ll;
  static T op(const T &a, const T &b) { return min(a, b); }
  static constexpr T identity() { return numeric_limits< T >::max(); }
};

struct RangeMax {
  using T = ll;
  static T op(const T &a, const T &b) { return max(a, b); }
  static constexpr T identity() { return numeric_limits< T >::min(); }
};

struct RangeSum {
  using T = ll;
  static T op(const T &a, const T &b) { return a + b; }
  static constexpr T identity() { return 0; }
};

/// }}}--- ///

// MinAdd m + x
// MinSet m
// SumAdd m * n + x
// SumSet m * n

struct RangeMinAdd {
  using M = ll;
  using X = RangeMin::T;
  static M op(const M &a, const M &b) { return a + b; }
  static constexpr M identity() { return 0; }
  static X actInto(const M &m, ll, ll, const X &x) { return m + x; }
};

struct RangeMinSet {
  using M = ll;
  using X = RangeMin::T;
  static M op(const M &a, const M &) { return a; }
  static constexpr M identity() { return numeric_limits< M >::min(); }
  static X actInto(const M &m, ll, ll, const X &) { return m; }
};

struct RangeSumAdd {
  using M = ll;
  using X = RangeSum::T;
  static M op(const M &a, const M &b) { return a + b; }
  static constexpr M identity() { return 0; }
  static X actInto(const M &m, ll, ll n, const X &x) { return m * n + x; }
};

struct RangeSumSet {
  using M = ll;
  using X = RangeSum::T;
  static M op(const M &a, const M &) { return a; }
  static constexpr M identity() { return numeric_limits< M >::min(); }
  static X actInto(const M &m, ll, ll n, const X &) { return m * n; }
};

/// }}}--- ///

template < class Monoid, class M_act >
using RBTSeq = RedBlackTreeSequenceBase< Monoid, M_act, false >;
template < class Monoid, class M_act >
using PersistentRBTSeq = RedBlackTreeSequenceBase< Monoid, M_act, true >;

using Node = PersistentRBTSeq< RangeSum, RangeSumAdd >;
Node *seq = nullptr;

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  int n, q;
  cin >> n >> q;
  // assert(n <= 5000);
  vector<int> a(n);
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  build(seq, a.begin(), a.end());
  // if(n > 5000) {
  //   return 0;
  // }
  while(q--) {
    assert(seq->level <= 18);
    // dump((int)seq->level);
    int t;
    cin >> t;
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    switch(t) {
    case 1: {
      int v;
      cin >> v;
      act(seq, a, b + 1, v);
      break;
    }
    case 2: {
      int c, d;
      cin >> c >> d;
      c--;
      d--;
      auto s = copy(seq, c, d + 1);
      Node *sl, *sr, *tl, *tr;
      tie(sl, sr) = split(seq, b + 1);
      tie(tl, tr) = split(sl, a);
      delete tr;
      seq = merge(merge(tl, s), sr);
      break;
    }
    case 3: {
      cout << query(seq, a, b + 1) << "\n";
      break;
    }
    }
  }
  return 0;
}

Submission Info

Submission Time
Task D - グラフではない
User luma
Language C++14 (GCC 5.4.1)
Score 0
Code Size 13294 Byte
Status TLE
Exec Time 5971 ms
Memory 68424 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 2
AC × 16
TLE × 6
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_largerandom_t1_01.txt, subtask1_largerandom_t1_02.txt, subtask1_largerandom_t2_03.txt, subtask1_largerandom_t2_04.txt, subtask1_largespecial01.txt, subtask1_largespecial02.txt, subtask1_largespecial03.txt, subtask1_largespecial04.txt, subtask1_largespecial05.txt, subtask1_largespecial06.txt, subtask1_smallrandom_01.txt, subtask1_smallrandom_02.txt, subtask1_smallrandom_03.txt, subtask1_smallrandom_04.txt, subtask1_smallrandom_05.txt, subtask1_smallrandom_06.txt, subtask1_smallrandom_07.txt, subtask1_smallrandom_08.txt, subtask1_smallrandom_09.txt, subtask1_smallrandom_10.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 1 ms 256 KB
subtask0_sample_02.txt AC 1 ms 384 KB
subtask1_largerandom_t1_01.txt TLE 5703 ms -550652 KB
subtask1_largerandom_t1_02.txt TLE 5971 ms -551668 KB
subtask1_largerandom_t2_03.txt TLE 5484 ms -559744 KB
subtask1_largerandom_t2_04.txt TLE 5649 ms -560520 KB
subtask1_largespecial01.txt TLE 5659 ms -558016 KB
subtask1_largespecial02.txt TLE 5480 ms -564844 KB
subtask1_largespecial03.txt AC 131 ms 48248 KB
subtask1_largespecial04.txt AC 144 ms 68424 KB
subtask1_largespecial05.txt AC 135 ms 57416 KB
subtask1_largespecial06.txt AC 57 ms 1408 KB
subtask1_smallrandom_01.txt AC 2 ms 1024 KB
subtask1_smallrandom_02.txt AC 2 ms 1024 KB
subtask1_smallrandom_03.txt AC 2 ms 1024 KB
subtask1_smallrandom_04.txt AC 2 ms 1024 KB
subtask1_smallrandom_05.txt AC 2 ms 1024 KB
subtask1_smallrandom_06.txt AC 2 ms 1024 KB
subtask1_smallrandom_07.txt AC 2 ms 1024 KB
subtask1_smallrandom_08.txt AC 2 ms 1024 KB
subtask1_smallrandom_09.txt AC 2 ms 1024 KB
subtask1_smallrandom_10.txt AC 2 ms 1024 KB