Submission #3609566
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;
// #undef DEBUG
// #define DEBUG
// DEBUG {{{
#include <stack>
#include <tuple>
#include <valarray>
#include <vector>
// clang-format off
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":", ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream &o, tuple<T...> const &t){ o << "("; _ot<0>(o, t); o << ")"; return o; }
template<class T, class U> ostream & operator<<(ostream &o, pair<T, U> const &p) { o << "(" << p.first << ", " << p.second << ")"; return o; }
template < class T > ostream &operator<<(ostream &o, const stack<T> &a) { o << "{"; for(auto tmp = a; tmp.size(); tmp.pop()) o << (a.size() == tmp.size() ? "" : ", ") << tmp.top(); o << "}"; return o; }
#ifdef DEBUG
#if !defined(DEBUG_OUT)
#define DEBUG_OUT cerr
#endif
#if !defined(DEBUG_LEFT)
#define DEBUG_LEFT "\e[1;36m"
#endif
#if !defined(DEBUG_RIGHT)
#define DEBUG_RIGHT ":\e[m"
#endif
#define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);DEBUG_OUT<<DEBUG_LEFT<<__LINE__ << DEBUG_RIGHT << " " <<#__VA_ARGS__<<" = "<<__debug_tap<<endl;}()
template < class T > inline void dump2D(T &d, size_t sizey, size_t sizex) { for(size_t i = 0; i < sizey; i++) { DEBUG_OUT << "\t"; for(size_t j = 0; j < sizex; j++) DEBUG_OUT << d[i][j] << (j + 1 == sizex ? "" : "\t"); DEBUG_OUT << endl; } }
template < class T, class = typename iterator_traits< typename T::iterator >::value_type, class = typename enable_if<!is_same<T, string>::value>::type > ostream &operator<<(ostream &o, const T &a) { o << "{"; for(auto ite = a.begin(); ite != a.end(); ++ite) o << (ite == a.begin() ? "" : ", ") << *ite; o << "}"; return o; }
#else
#define dump(...) (42)
#define dump2D(...) (42)
template < class T, class = typename iterator_traits< typename T::iterator >::value_type, class = typename enable_if<!is_same<T, string>::value>::type > ostream &operator<<(ostream &o, const T &a) { for(auto ite = a.begin(); ite != a.end(); ++ite) o << (ite == a.begin() ? "" : " ") << *ite; return o; }
#endif
// clang-format on
// }}}
/// --- 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;
auto b = &(*(new Node) = *a);
return b;
}
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;
}
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);
for(int i = 0; i < n; i++) {
int a;
cin >> a;
push_back(seq, a);
}
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);
erase(seq, a, b + 1);
insert(seq, a, s);
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 |
14787 Byte |
Status |
MLE |
Exec Time |
1365 ms |
Memory |
1388660 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 100 |
Status |
|
|
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 |
MLE |
1365 ms |
1388660 KB |
subtask1_largerandom_t1_02.txt |
MLE |
1328 ms |
1388160 KB |
subtask1_largerandom_t2_03.txt |
MLE |
1326 ms |
1385984 KB |
subtask1_largerandom_t2_04.txt |
MLE |
1324 ms |
1380736 KB |
subtask1_largespecial01.txt |
MLE |
1332 ms |
1388160 KB |
subtask1_largespecial02.txt |
MLE |
1333 ms |
1388160 KB |
subtask1_largespecial03.txt |
MLE |
1326 ms |
1388160 KB |
subtask1_largespecial04.txt |
MLE |
1331 ms |
1388160 KB |
subtask1_largespecial05.txt |
MLE |
1339 ms |
1388316 KB |
subtask1_largespecial06.txt |
AC |
59 ms |
1408 KB |
subtask1_smallrandom_01.txt |
AC |
3 ms |
1280 KB |
subtask1_smallrandom_02.txt |
AC |
3 ms |
1280 KB |
subtask1_smallrandom_03.txt |
AC |
3 ms |
1152 KB |
subtask1_smallrandom_04.txt |
AC |
3 ms |
1280 KB |
subtask1_smallrandom_05.txt |
AC |
3 ms |
1280 KB |
subtask1_smallrandom_06.txt |
AC |
3 ms |
1280 KB |
subtask1_smallrandom_07.txt |
AC |
3 ms |
1152 KB |
subtask1_smallrandom_08.txt |
AC |
3 ms |
1280 KB |
subtask1_smallrandom_09.txt |
AC |
3 ms |
1152 KB |
subtask1_smallrandom_10.txt |
AC |
3 ms |
1152 KB |