Submission #2860599


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]);
	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 4913 Byte
Status WA
Exec Time 809 ms
Memory 590720 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 2
AC × 15
WA × 7
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 WA 809 ms 590336 KB
subtask1_largerandom_t1_02.txt WA 806 ms 590336 KB
subtask1_largerandom_t2_03.txt WA 675 ms 590720 KB
subtask1_largerandom_t2_04.txt WA 678 ms 590720 KB
subtask1_largespecial01.txt WA 232 ms 275456 KB
subtask1_largespecial02.txt AC 634 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