Submission #2860486
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using T = ll;
using U = ll;
const T id1 = 0;
const U id2 = 0;
T op(T l, T r) {
return l + r;
}
enum COL { BLACK, RED };
struct node;
node *update(node *t);
struct node {
T val, all;
U lazy;
node *ch[2];
COL color;
int level;
int size;
node() {}
void init(T v) {
val = v;
lazy = id2;
all = v;
color = BLACK;
level = 0;
size = 1;
ch[0] = ch[1] = nullptr;
}
void init(node *l, node *r) {
val = id1;
lazy = id2;
color = RED;
ch[0] = l;
ch[1] = r;
update(this);
}
};
const int pmax = 2.5e7;
node pool[pmax];
int it = 0;
int count(node *t) { return !t ? 0 : t->size; }
T que(node *t) { return !t ? id1 : t->all; }
node *update(node *t) {
t->size = count(t->ch[0]) + count(t->ch[1]) + (!t->ch[0] || !t->ch[1]);
t->all = op(que(t->ch[0]), op(t->val, que(t->ch[1])));
t->level = (t->ch[0] ? t->ch[0]->level + (t->ch[0]->color == BLACK) : 0);
return t;
}
node *new_leaf(T v) {
assert(it < pmax);
pool[it].init(v);
return pool + it++;
}
node *new_node(node *l, node *r) {
assert(it < pmax);
pool[it].init(l, r);
return pool + it++;
}
node *dup_node(node *t) {
assert(it < pmax);
pool[it] = *t;
return pool + it++;
}
bool push(node *t) {
if (t->lazy == id2) return false;
for (int i = 0; i < 2; i++) if (t->ch[i]) {
t->ch[i] = dup_node(t->ch[i]);
t->ch[i]->lazy += t->lazy;
if (!t->ch[i]->ch[0]) t->ch[i]->val += t->lazy;
t->ch[i]->all += t->lazy * t->ch[i]->size;
}
t->lazy = id2;
return true;
}
node *rotate(node *t, int b) {
node *s;
if (push(t)) s = t->ch[1 - b];
else s = dup_node(t->ch[1 - b]);
push(s);
t->ch[1 - b] = s->ch[b];
s->ch[b] = t;
update(t);
return update(s);
}
node *submerge(node *l, node *r) {
if (l->level < r->level) {
push(r = dup_node(r));
node *c = r->ch[0] = submerge(l, r->ch[0]);
if (r->color == BLACK && c->color == RED && c->ch[0] && c->ch[0]->color == RED) {
if (r->ch[1]->color == BLACK) {
r->color = RED;
c->color = BLACK;
return rotate(r, 1);
}
c->color = BLACK;
r->ch[1]->color = BLACK;
r->color = RED;
}
return update(r);
}
if (l->level > r->level) {
push(l = dup_node(l));
node *c = l->ch[1] = submerge(l->ch[1], r);
if (l->color == BLACK && c->color == RED && c->ch[1] && c->ch[1]->color == RED) {
if (l->ch[0]->color == BLACK) {
l->color = RED;
c->color = BLACK;
return rotate(l, 0);
}
l->ch[0]->color = BLACK;
c->color = BLACK;
l->color = RED;
}
return update(l);
}
return new_node(l, r);
}
node *merge(node *l, node *r) {
if (!l) return r;
if (!r) return l;
node *c = submerge(l, r);
c->color = BLACK;
return c;
}
pair<node*, node*> split(node *t, int k) {
if (!t) return make_pair(nullptr, nullptr);
if (k == 0) return make_pair(nullptr, t);
if (k >= count(t)) return make_pair(t, nullptr);
push(t = dup_node(t));
int c = count(t->ch[0]);
node *l = t->ch[0], *r = t->ch[1];
if (k < c) {
pair<node*, node*> p = split(l, k);
return make_pair(p.first, merge(p.second, r));
}
if (k > c) {
pair<node*, node*> p = split(r, k - c);
return make_pair(merge(l, p.first), p.second);
}
return make_pair(l, r);
}
T find(node *t, int l, int r, U lazy = id2) {
if (!t || r <= 0 || t->size <= l) return id1;
if (l <= 0 && t->size <= r) return t->all + lazy * t->size;
lazy += t->lazy;
int c = count(t->ch[0]);
return op(find(t->ch[0], l, r, lazy), find(t->ch[1], l - c, r - c, lazy));
}
node *update(node *t, int l, int r, U val) {
if (!t || r <= 0 || t->size <= l) return t;
t = dup_node(t);
if (l <= 0 && t->size <= r) {
t->lazy += val;
if (!t->ch[0]) t->val += val;
t->all += val * t->size;
return t;
}
push(t);
int c = t->ch[0]->size;
t->ch[0] = update(t->ch[0], l, r, val);
t->ch[1] = update(t->ch[1], l - c, r - c, val);
return update(t);
}
node *copy(node *t, int a, int b, int c, int d) {
pair<node*, node*> p1 = split(t, a), p2 = split(p1.second, b - a);
pair<node*, node*> q1 = split(t, c), q2 = split(q1.second, d - c);
return merge(p1.first, merge(q2.first, p2.second));
}
node* build(const vector<T>& x, int lb, int ub) {
if (ub - lb == 1) return new_leaf(x[lb]);
int m = (lb + ub) >> 1;
return merge(build(x, lb, m), build(x, m, ub));
}
void print(node *t, int lb, int ub, U lazy = id2) {
if (!t) return;
if (ub - lb == 1) {
printf(" %lld", t->val + lazy);
return;
}
lazy += t->lazy;
int m = lb + t->ch[0]->size;
print(t->ch[0], lb, m, lazy);
print(t->ch[1], m, ub, lazy);
}
void store(node *t, vector<T>& x, int lb, int ub, U lazy = id2) {
if (ub - lb == 1) {
x[lb] = t->val + lazy;
return;
}
lazy += t->lazy;
int m = lb + t->ch[0]->size;
store(t->ch[0], x, lb, m, lazy);
store(t->ch[1], x, m, ub, lazy);
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0);
int N, Q;
cin >> N >> Q;
vector<ll> x(N);
for (int i = 0; i < N; i++) {
cin >> x[i];
}
node *root = build(x, 0, N);
while (Q--) {
int com;
cin >> com;
switch (com)
{
case 1: {
int a, b, v;
cin >> a >> b >> v; --a;
root = update(root, a, b, v);
}
break;
case 2: {
int a, b, c, d;
cin >> a >> b >> c >> d; --a, --c;
root = copy(root, a, b, c, d);
}
break;
case 3: {
int a, b;
cin >> a >> b; --a;
printf("%lld\n", find(root, a, b));
}
break;
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - グラフではない |
User |
kazuma |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
5585 Byte |
Status |
RE |
Exec Time |
882 ms |
Memory |
1370240 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 |
5 ms |
384 KB |
subtask0_sample_02.txt |
AC |
1 ms |
256 KB |
subtask1_largerandom_t1_01.txt |
RE |
751 ms |
1369728 KB |
subtask1_largerandom_t1_02.txt |
RE |
752 ms |
1369600 KB |
subtask1_largerandom_t2_03.txt |
RE |
793 ms |
1370240 KB |
subtask1_largerandom_t2_04.txt |
RE |
792 ms |
1370240 KB |
subtask1_largespecial01.txt |
AC |
239 ms |
320768 KB |
subtask1_largespecial02.txt |
RE |
882 ms |
1369728 KB |
subtask1_largespecial03.txt |
AC |
91 ms |
29568 KB |
subtask1_largespecial04.txt |
AC |
92 ms |
36352 KB |
subtask1_largespecial05.txt |
AC |
91 ms |
32128 KB |
subtask1_largespecial06.txt |
AC |
59 ms |
5504 KB |
subtask1_smallrandom_01.txt |
AC |
1 ms |
512 KB |
subtask1_smallrandom_02.txt |
AC |
1 ms |
512 KB |
subtask1_smallrandom_03.txt |
AC |
1 ms |
512 KB |
subtask1_smallrandom_04.txt |
AC |
1 ms |
512 KB |
subtask1_smallrandom_05.txt |
AC |
1 ms |
512 KB |
subtask1_smallrandom_06.txt |
AC |
1 ms |
512 KB |
subtask1_smallrandom_07.txt |
AC |
1 ms |
512 KB |
subtask1_smallrandom_08.txt |
AC |
1 ms |
512 KB |
subtask1_smallrandom_09.txt |
AC |
1 ms |
512 KB |
subtask1_smallrandom_10.txt |
AC |
1 ms |
512 KB |