SlidingWindowAggregation<T> (Library Checker: Queue Operate All Composite) (CpLibrary.Verify/Collections/SlidingWindowAggregation.cs)

• View this file on GitHub
• Last update: 2025-08-03 02:07:13+09:00
• Problem: https://judge.yosupo.jp/problem/queue_operate_all_composite

Depends on

• CpLibrary/Collections/SlidingWindowAggregation.cs
• CpLibrary/IO/Scanner.cs

Code

using CpLibrary.Collections;
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using ModInt = AtCoder.StaticModInt<AtCoder.Mod998244353>;

namespace CpLibrary.Verify.Collections
{
	// competitive-verifier: document_title SlidingWindowAggregation<T> (Library Checker: Queue Operate All Composite)
	internal class SlidingWindowAggregationTest : CompetitiveVerifier.ProblemSolver
	{
		public override string Url => "https://judge.yosupo.jp/problem/queue_operate_all_composite";
		public override void Solve()
		{
			var sr = new Scanner(new StreamReader(Console.OpenStandardInput()));

			var swag = new SlidingWindowAggregation<(ModInt a, ModInt b)>((x, y) => (x.a * y.a, y.a * x.b + y.b));

			var q = sr.ReadInt();
			for (int i = 0; i < q; i++)
			{
				var query = sr.ReadInt();
				if (query == 0)
				{
					var (a, b) = sr.ReadValue<int, int>();
					swag.Push((a, b));
				}
				if (query == 1)
				{
					swag.Pop();
				}
				if (query == 2)
				{
					var x = sr.ReadInt();
					if (swag.Count == 0)
					{
						Console.WriteLine(x);
						continue;
					}
					var ret = swag.Prod();
					Console.WriteLine(ret.a * x + ret.b);
				}
			}
		}
	}
}

Test cases

Env	Name	Status	Elapsed	Memory
	example_00	AC	63 ms	29 MB
	example_01	AC	66 ms	29 MB
	large_max_00	AC	405 ms	59 MB
	large_max_01	AC	372 ms	59 MB
	large_min_00	AC	403 ms	48 MB
	large_min_01	AC	425 ms	47 MB
	large_triangle_00	AC	437 ms	54 MB
	large_triangle_01	AC	463 ms	55 MB
	max_random_00	AC	394 ms	62 MB
	max_random_01	AC	438 ms	62 MB
	max_random_02	AC	430 ms	62 MB
	random_00	AC	324 ms	53 MB
	random_01	AC	417 ms	55 MB
	random_02	AC	122 ms	41 MB
	small_00	AC	55 ms	29 MB
	small_01	AC	65 ms	29 MB
	small_02	AC	57 ms	29 MB
	small_03	AC	50 ms	29 MB
	small_04	AC	55 ms	29 MB

Back to top page