Submission #3609551
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};
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 {l, 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);
}
while(q--) {
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 |
12422 Byte |
Status |
RE |
Exec Time |
98 ms |
Memory |
1408 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 |
RE |
96 ms |
256 KB |
subtask1_largerandom_t1_02.txt |
RE |
96 ms |
256 KB |
subtask1_largerandom_t2_03.txt |
RE |
98 ms |
256 KB |
subtask1_largerandom_t2_04.txt |
RE |
97 ms |
256 KB |
subtask1_largespecial01.txt |
RE |
96 ms |
256 KB |
subtask1_largespecial02.txt |
RE |
96 ms |
256 KB |
subtask1_largespecial03.txt |
RE |
97 ms |
256 KB |
subtask1_largespecial04.txt |
RE |
96 ms |
256 KB |
subtask1_largespecial05.txt |
RE |
96 ms |
256 KB |
subtask1_largespecial06.txt |
AC |
58 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 |
2 ms |
1152 KB |
subtask1_smallrandom_04.txt |
WA |
2 ms |
1280 KB |
subtask1_smallrandom_05.txt |
AC |
3 ms |
1280 KB |
subtask1_smallrandom_06.txt |
AC |
2 ms |
1280 KB |
subtask1_smallrandom_07.txt |
WA |
2 ms |
1152 KB |
subtask1_smallrandom_08.txt |
WA |
3 ms |
1280 KB |
subtask1_smallrandom_09.txt |
AC |
2 ms |
1152 KB |
subtask1_smallrandom_10.txt |
AC |
2 ms |
1152 KB |