Submission #1497764


Source Code Expand

using System.Linq;
using System;
class Z
{
	static int[] G() => Console.ReadLine().Split().Select(int.Parse).ToArray();
	static void Main()
	{
		var I = G();
		int N = I[0], Q = I[1];
		var t = G().ToT(0, N);
		for (var i = 0; i < Q; i++)
		{
			I = G();
			int a = I[1] - 1, b = I[2];
			if (I[0] == 1) t = t[0, a].Join(t[a, b].Add(I[3])).Join(t[b, N]);
			else if (I[0] == 2) t = t[0, a].Join(t[I[3] - 1, I[4]]).Join(t[b, N]);
			else Console.WriteLine(t[a, b].Sum());
		}
	}
}
class T
{
	public readonly T L, R;
	public readonly long V, S, Lz;
	public readonly int H, C;
	public T this[int l, int r] => this.Left(r).Right(l);
	public T(T l, long v, T r, long s, long lz, int h, int c)
	{
		L = l;
		V = v;
		R = r;
		S = s;
		Lz = lz;
		H = h;
		C = c;
	}
	public T(T l, long v, T r, int lz = 0)
	{
		C = 1 + l.Count() + r.Count();
		S = v + l.Sum() + r.Sum();
		Lz = lz;
		var lh = l.Height();
		var rh = r.Height();
		if (lh > rh + 1)
		{
			l = l.Update();
			if (l.L.Height() >= l.R.Height())
			{
				V = l.V;
				L = l.L;
				R = new T(l.R, v, r);
			}
			else
			{
				var lr = l.R.Update();
				V = lr.V;
				L = new T(l.L, l.V, lr.L);
				R = new T(lr.R, v, r);
			}
		}
		else if (rh > lh + 1)
		{
			r = r.Update();
			if (r.R.Height() >= r.L.Height())
			{
				V = r.V;
				L = new T(l, v, r.L);
				R = r.R;
			}
			else
			{
				var rl = r.L.Update();
				V = rl.V;
				L = new T(l, v, rl.L);
				R = new T(rl.R, r.V, r.R);
			}
		}
		else
		{
			L = l;
			R = r;
			V = v;
		}
		H = 1 + Math.Max(L.Height(), R.Height());
	}
}
static class Func
{
	public static T ToT(this int[] x, int l, int r)
	{
		if (l >= r) return null;
		var n = (l + r) / 2;
		return Join(x.ToT(l, n), x[n], x.ToT(n + 1, r));
	}
	public static long Sum(this T t) => t == null ? 0 : t.S;
	public static T Add(this T t, long lz) => t == null || lz == 0 ? t : new T(t.L, t.V, t.R, t.S + t.C * lz, t.Lz + lz, t.H, t.C);
	public static T Update(this T t) => t == null || t.Lz == 0 ? t : new T(t.L.Add(t.Lz), t.V + t.Lz, t.R.Add(t.Lz), t.S, 0, t.H, t.C);
	public static int Count(this T t) => t == null ? 0 : t.C;
	public static int Height(this T t) => t == null ? 0 : t.H;
	public static T Join(this T t1, T t2)
	{
		if (t1 == null) return t2;
		if (t2 == null) return t1;
		var c = t1.Count() - 1;
		return Join(t1.Left(c), t1.Right(c).V, t2);
	}
	static T Join(T t1, long x, T t2)
	{
		var h1 = t1.Height();
		var h2 = t2.Height();
		if (Math.Abs(h1 - h2) <= 1) return new T(t1, x, t2);
		if (h1 > h2)
		{
			t1 = t1.Update();
			return new T(t1.L, t1.V, Join(t1.R, x, t2));
		}
		t2 = t2.Update();
		return new T(Join(t1, x, t2.L), t2.V, t2.R);
	}
	public static T Left(this T t, int r)
	{
		if (t == null || 0 >= r) return null;
		t = t.Update();
		var lc = t.L.Count();
		return r <= lc ? t.L.Left(r) : Join(t.L, t.V, t.R.Left(r - lc - 1));
	}
	public static T Right(this T t, int l)
	{
		if (t == null || l >= t.Count()) return null;
		t = t.Update();
		var lc = t.L.Count();
		return lc < l ? t.R.Right(l - lc - 1) : Join(t.L.Right(l), t.V, t.R);
	}
}

Submission Info

Submission Time
Task D - グラフではない
User selpo
Language C# (Mono 4.6.2.0)
Score 100
Code Size 3179 Byte
Status AC
Exec Time 3310 ms
Memory 48208 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 22
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 24 ms 13396 KB
subtask0_sample_02.txt AC 24 ms 11348 KB
subtask1_largerandom_t1_01.txt AC 3292 ms 41980 KB
subtask1_largerandom_t1_02.txt AC 3310 ms 44032 KB
subtask1_largerandom_t2_03.txt AC 3157 ms 46016 KB
subtask1_largerandom_t2_04.txt AC 3130 ms 48116 KB
subtask1_largespecial01.txt AC 2356 ms 48208 KB
subtask1_largespecial02.txt AC 2093 ms 45936 KB
subtask1_largespecial03.txt AC 1581 ms 44500 KB
subtask1_largespecial04.txt AC 2124 ms 46892 KB
subtask1_largespecial05.txt AC 1832 ms 44708 KB
subtask1_largespecial06.txt AC 1006 ms 16596 KB
subtask1_smallrandom_01.txt AC 25 ms 11348 KB
subtask1_smallrandom_02.txt AC 25 ms 11348 KB
subtask1_smallrandom_03.txt AC 25 ms 11348 KB
subtask1_smallrandom_04.txt AC 25 ms 9300 KB
subtask1_smallrandom_05.txt AC 24 ms 9300 KB
subtask1_smallrandom_06.txt AC 25 ms 9300 KB
subtask1_smallrandom_07.txt AC 25 ms 11348 KB
subtask1_smallrandom_08.txt AC 25 ms 9300 KB
subtask1_smallrandom_09.txt AC 25 ms 13396 KB
subtask1_smallrandom_10.txt AC 25 ms 11348 KB