Submission #2861147
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;
}
struct node;
node *update(node *t);
struct node {
T val, all;
U lazy;
node *ch[2];
int dep, size;
node() {}
void init(T v) {
val = all = v;
lazy = id2;
dep = size = 1;
ch[0] = ch[1] = nullptr;
}
void init(node* l, node* r) {
val = id1;
lazy = id2;
ch[0] = l, ch[1] = r;
update(this);
}
};
const int pmax = 2.5e7;
node pool[pmax];
int it = 0;
int depth(node *t) { return t ? t->dep : 0; }
int count(node *t) { return t ? t->size : 0; }
int que(node *t) { return t ? t->all : id1; }
node *update(node *t) {
t->dep = max(depth(t->ch[0]), depth(t->ch[1])) + 1;
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])));
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 *fix(node *t) {
int dd = depth(t->ch[0]) - depth(t->ch[1]);
assert (abs(dd) <= 2);
if (abs(dd) < 2) return t;
int b = dd < 0;
if (depth(t->ch[b]->ch[!b]) > depth(t->ch[b]->ch[b])) {
t->ch[b] = rotate(dup_node(t->ch[b]), b);
}
return rotate(t, !b);
}
node *merge(node *l, node *r) {
if (!l) return r;
if (!r) return l;
if (l->dep == r->dep) return new_node(l, r);
if (l->dep < r->dep) {
push(r = dup_node(r));
r->ch[0] = merge(l, r->ch[0]);
return fix(update(r));
}
push(l = dup_node(l));
l->ch[1] = merge(l->ch[1], r);
return fix(update(l));
}
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 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;
}
if (it >= pmax / 2) {
store(root, x, 0, N);
it = 0;
root = build(x, 0, N);
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - グラフではない |
User |
kazuma |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4938 Byte |
Status |
WA |
Exec Time |
817 ms |
Memory |
590720 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 |
4 ms |
256 KB |
subtask0_sample_02.txt |
AC |
1 ms |
256 KB |
subtask1_largerandom_t1_01.txt |
WA |
817 ms |
590336 KB |
subtask1_largerandom_t1_02.txt |
WA |
813 ms |
590336 KB |
subtask1_largerandom_t2_03.txt |
WA |
685 ms |
590720 KB |
subtask1_largerandom_t2_04.txt |
WA |
684 ms |
590720 KB |
subtask1_largespecial01.txt |
WA |
232 ms |
275456 KB |
subtask1_largespecial02.txt |
AC |
658 ms |
590592 KB |
subtask1_largespecial03.txt |
AC |
92 ms |
25472 KB |
subtask1_largespecial04.txt |
WA |
93 ms |
30208 KB |
subtask1_largespecial05.txt |
WA |
92 ms |
28032 KB |
subtask1_largespecial06.txt |
AC |
60 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 |
384 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 |