Submission #1513443
Source Code Expand
#include "bits/stdc++.h"
#include <random>
using namespace std;
mt19937 mt(0);
struct node {
int sz;
long long val, add, sum;
shared_ptr<node> lchild, rchild;
node(long long val, int sz, long long add, long long sum, shared_ptr<node> lchild, shared_ptr<node> rchild)
: val(val), sz(sz), add(add), sum(sum), lchild(lchild), rchild(rchild) {}
};
int size(shared_ptr<node> t) { return !t ? 0 : t->sz; }
long long sum(shared_ptr<node> t) { return !t ? 0 : t->sum; }
shared_ptr<node> add(shared_ptr<node> v, long long a) {
if (!v) return NULL;
int sz = v->sz;
return shared_ptr<node>(new node(v->val, sz, v->add + a, v->sum + a * sz, v->lchild, v->rchild));
}
shared_ptr<node> singleton(long long val) {
return shared_ptr<node>(new node(val, 1, 0, val, NULL, NULL));
}
shared_ptr<node> make_node(long long val, shared_ptr<node> left, shared_ptr<node> right, long long a = 0) { //+= a
int sz = size(left) + size(right) + 1;
return shared_ptr<node>(new node(val, sz, a, sum(left) + sum(right) + val + a * sz, left, right));
}
shared_ptr<node> merge(shared_ptr<node> left, shared_ptr<node> right) {
if (!left || !right) return !left ? right : left;
if (int(mt() % (size(left) + size(right)) < size(left))) {
if (left->add == 0) {
return make_node(left->val + left->add, left->lchild, merge(left->rchild, right));
}
shared_ptr<node> lv = add(left->lchild, left->add);
shared_ptr<node> rv = merge(add(left->rchild, left->add), right);
return make_node(left->val + left->add, lv, rv);
} else {
if (right->add == 0) {
return make_node(right->val + right->add, merge(left, right->lchild), right->rchild);
}
shared_ptr<node> lv = merge(left, add(right->lchild, right->add));
shared_ptr<node> rv = add(right->rchild, right->add);
return make_node(right->val + right->add, lv, rv);
}
}
pair<shared_ptr<node>, shared_ptr<node>> split(shared_ptr<node> t, int k) { //[0, k), [k, n)
if (k == 0) return pair<shared_ptr<node>, shared_ptr<node>>(NULL, t);
if (k >= size(t)) return pair<shared_ptr<node>, shared_ptr<node>>(t, NULL);
if (size(t->lchild) >= k) {
auto left = split(t->lchild, k);
auto rv = make_node(t->val, left.second, t->rchild, t->add);
if (t->add == 0) return make_pair(left.first, rv);
return make_pair(add(left.first, t->add), rv);
} else {
auto right = split(t->rchild, k - size(t->lchild) - 1);
auto lv = make_node(t->val, t->lchild, right.first, t->add);
if (t->add == 0) return make_pair(lv, right.second);
return make_pair(lv, add(right.second, t->add));
}
}
int main() {
int n, q;
cin >> n >> q;
shared_ptr<node> tree = NULL;
for (int i = 0; i < n; i ++) {
int x;
cin >> x;
tree = merge(tree, singleton(x));
}
while (q --) {
int type, a, b, c, d, v;
cin >> type;
if (type == 1) {
cin >> a >> b >> v;
auto y = split(tree, b);
auto x = split(y.first, a - 1);
tree = merge(x.first, merge(add(x.second, v), y.second));
} else if (type == 2) {
cin >> a >> b >> c >> d;
auto y = split(split(tree, d).first, c - 1).second;
auto x = split(tree, b);
auto left = split(x.first, a - 1).first;
auto right = x.second;
tree = merge(left, merge(y, right));
} else {
cin >> a >> b;
long long ans = sum(split(split(tree, b).first, a - 1).second);
cout << ans << endl;
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - グラフではない |
User |
KokiYmgch |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
4310 Byte |
Status |
AC |
Exec Time |
4242 ms |
Memory |
25216 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 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 |
256 KB |
subtask1_largerandom_t1_01.txt |
AC |
4242 ms |
23040 KB |
subtask1_largerandom_t1_02.txt |
AC |
4214 ms |
24576 KB |
subtask1_largerandom_t2_03.txt |
AC |
3803 ms |
23424 KB |
subtask1_largerandom_t2_04.txt |
AC |
3783 ms |
25216 KB |
subtask1_largespecial01.txt |
AC |
2682 ms |
23552 KB |
subtask1_largespecial02.txt |
AC |
2648 ms |
23168 KB |
subtask1_largespecial03.txt |
AC |
754 ms |
23168 KB |
subtask1_largespecial04.txt |
AC |
775 ms |
23936 KB |
subtask1_largespecial05.txt |
AC |
768 ms |
23840 KB |
subtask1_largespecial06.txt |
AC |
327 ms |
1408 KB |
subtask1_smallrandom_01.txt |
AC |
2 ms |
256 KB |
subtask1_smallrandom_02.txt |
AC |
2 ms |
256 KB |
subtask1_smallrandom_03.txt |
AC |
2 ms |
256 KB |
subtask1_smallrandom_04.txt |
AC |
2 ms |
256 KB |
subtask1_smallrandom_05.txt |
AC |
2 ms |
256 KB |
subtask1_smallrandom_06.txt |
AC |
2 ms |
256 KB |
subtask1_smallrandom_07.txt |
AC |
2 ms |
256 KB |
subtask1_smallrandom_08.txt |
AC |
2 ms |
256 KB |
subtask1_smallrandom_09.txt |
AC |
2 ms |
256 KB |
subtask1_smallrandom_10.txt |
AC |
2 ms |
256 KB |