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
AC × 2
AC × 17
RE × 5
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