結果
問題 | No.2650 [Cherry 6th Tune *] セイジャク |
ユーザー | tobisatis |
提出日時 | 2024-02-23 21:29:44 |
言語 | C# (.NET 8.0.203) |
結果 |
AC
|
実行時間 | 1,696 ms / 2,500 ms |
コード長 | 7,889 bytes |
コンパイル時間 | 15,094 ms |
コンパイル使用メモリ | 157,692 KB |
実行使用メモリ | 207,424 KB |
最終ジャッジ日時 | 2024-02-23 21:30:52 |
合計ジャッジ時間 | 54,375 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge16 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 91 ms
33,444 KB |
testcase_01 | AC | 89 ms
33,444 KB |
testcase_02 | AC | 494 ms
48,608 KB |
testcase_03 | AC | 283 ms
43,684 KB |
testcase_04 | AC | 1,163 ms
71,584 KB |
testcase_05 | AC | 887 ms
70,584 KB |
testcase_06 | AC | 497 ms
52,388 KB |
testcase_07 | AC | 979 ms
72,552 KB |
testcase_08 | AC | 370 ms
45,092 KB |
testcase_09 | AC | 1,664 ms
77,776 KB |
testcase_10 | AC | 1,657 ms
83,924 KB |
testcase_11 | AC | 1,660 ms
83,892 KB |
testcase_12 | AC | 1,696 ms
83,880 KB |
testcase_13 | AC | 1,668 ms
83,912 KB |
testcase_14 | AC | 1,653 ms
83,928 KB |
testcase_15 | AC | 1,678 ms
78,148 KB |
testcase_16 | AC | 1,547 ms
78,060 KB |
testcase_17 | AC | 1,556 ms
90,756 KB |
testcase_18 | AC | 1,536 ms
83,796 KB |
testcase_19 | AC | 1,534 ms
83,824 KB |
testcase_20 | AC | 1,538 ms
83,836 KB |
testcase_21 | AC | 1,541 ms
83,828 KB |
testcase_22 | AC | 1,560 ms
83,820 KB |
testcase_23 | AC | 1,489 ms
83,832 KB |
testcase_24 | AC | 1,480 ms
83,860 KB |
testcase_25 | AC | 1,490 ms
78,048 KB |
testcase_26 | AC | 1,479 ms
83,868 KB |
testcase_27 | AC | 1,482 ms
83,852 KB |
testcase_28 | AC | 1,483 ms
83,740 KB |
testcase_29 | AC | 1,471 ms
83,772 KB |
testcase_30 | AC | 1,492 ms
83,872 KB |
testcase_31 | AC | 1,539 ms
83,948 KB |
testcase_32 | AC | 682 ms
207,424 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (106 ms)。 MSBuild のバージョン 17.7.3+8ec440e68 (.NET) main -> /home/judge/data/code/bin/Release/net7.0/main.dll main -> /home/judge/data/code/bin/Release/net7.0/publish/
ソースコード
namespace AtCoder; #nullable enable using System.Numerics; static class Extensions { public static T[] Repeat<T>(this int time, Func<T> F) => Enumerable.Range(0, time).Select(_ => F()).ToArray(); } abstract class SegmentTree<TMonoid> { public interface IOperator { TMonoid IdentityElement { get; } TMonoid Operation(TMonoid x, TMonoid y); } public interface IBinarySearchOperator { bool F(TMonoid value); } public class Body<TOperator> where TOperator : struct, IOperator { public int BaseSize { get; init; } protected int Height { get; init; } protected TOperator Op { get; init; } protected TMonoid[] Values { get; init; } public Body(TMonoid[] initial, TOperator op = default) { Op = op; (BaseSize, Height) = (1, 0); while (BaseSize < initial.Length) (BaseSize, Height) = (BaseSize << 1, Height + 1); var size = BaseSize << 1; Values = new TMonoid[size]; for (var i = 0; i < size; i++) Values[i] = op.IdentityElement; for (var i = 0; i < initial.Length; i++) Values[i + BaseSize] = initial[i]; for (var i = BaseSize - 1; i > 0; i--) Update(i); } public TMonoid Product(int l, int r) { (l, r) = (l + BaseSize, r + BaseSize); var (resL, resR) = (Op.IdentityElement, Op.IdentityElement); while (l < r) { if ((l & 1) == 1) resL = Op.Operation(resL, Values[l++]); if ((r & 1) == 1) resR = Op.Operation(Values[--r], resR); (l, r) = (l >> 1, r >> 1); } return Op.Operation(resL, resR); } public void Set(int index, TMonoid value) { var j = index + BaseSize; Values[j] = value; for (var i = 1; i <= Height; i++) Update(j >> i); } // the result might be greater than n public int MinIndex<TMinIndexOperator>(TMinIndexOperator op = default) where TMinIndexOperator : struct, IBinarySearchOperator { if (!op.F(Values[1])) return BaseSize + 1; var product = Op.IdentityElement; var (res, w, i) = (0, BaseSize, 1); while (w > 0) { var p = Op.Operation(product, Values[i]); if (!op.F(p)) { res += w; i++; product = p; } w >>= 1; i <<= 1; } return res + 1; } protected void Update(int k) { Values[k] = Op.Operation(Values[k << 1], Values[(k << 1) + 1]); } } } abstract class LazySegmentTree<TMonoid, TFunction> { public interface IOperator : SegmentTree<TMonoid>.IOperator { TFunction IdentityFunction { get; } TMonoid Mapping(TFunction f, TMonoid x); TFunction Composition(TFunction f, TFunction g); } public class Body<TOperator> : SegmentTree<TMonoid>.Body<TOperator> where TOperator : struct, IOperator { TFunction[] Lazy { get; init; } public Body(TMonoid[] initial, TOperator op = default) : base(initial, op) { var size = BaseSize << 1; Lazy = new TFunction[size]; for (var i = 0; i < size; i++) Lazy[i] = op.IdentityFunction; } public new TMonoid Product(int l, int r) { if (l == r) return Op.IdentityElement; Ascend(l, r); return base.Product(l, r); } public new void Set(int index, TMonoid value) { var j = index + BaseSize; for (var i = Height; i >= 1; i--) Propagate(j >> i); Values[j] = value; for (var i = 1; i <= Height; i++) Update(j >> i); } public void Apply(int l, int r, TFunction f) { if (l == r) return; Ascend(l, r); (l, r) = (l + BaseSize, r + BaseSize); var (l2, r2) = (l, r); while (l2 < r2) { if ((l2 & 1) == 1) Apply(l2++, f); if ((r2 & 1) == 1) Apply(--r2, f); (l2, r2) = (l2 >> 1, r2 >> 1); } for (int i = 1; i <= Height; i++) { if (((l >> i) << i) != l) Update(l >> i); if (((r >> i) << i) != r) Update((r - 1) >> i); } } void Ascend(int l, int r) { (l, r) = (l + BaseSize, r + BaseSize); for (int i = Height; i >= 1; i--) { if (((l >> i) << i) != l) Propagate(l >> i); if (((r >> i) << i) != r) Propagate((r - 1) >> i); } } void Propagate(int k) { Apply(k << 1, Lazy[k]); Apply((k << 1) + 1, Lazy[k]); Lazy[k] = Op.IdentityFunction; } void Apply(int k, TFunction f) { Values[k] = Op.Mapping(f, Values[k]); if (k < BaseSize) Lazy[k] = Op.Composition(Lazy[k], f); } } } readonly struct Op : LazySegmentTree<int, int>.IOperator { public int IdentityFunction => -1; public int IdentityElement => -1; public int Composition(int f, int g) => Math.Max(f, g); public int Mapping(int f, int x) => Math.Max(f, x); public int Operation(int x, int y) => Math.Max(x, y); } class AtCoder { object? Solve() { var n = Int(); var _ = Int(); var ns = new HashSet<int>(); var xz = new int[n]; for (var i = 0; i < n; i++) { var x = Int(); xz[i] = x; ns.Add(x); } var t = Int(); var sounds = new (int, int)[t]; for (var i = 0; i < t; i++) { var l = Int(); var r = Int(); sounds[i] = (l, r); ns.Add(l); ns.Add(r); } var d = new Dictionary<int, int>(); { var l = new List<int>(ns); l.Sort(); for (var i = 0; i < l.Count; i++) { d[l[i]] = i; } } var tree = new LazySegmentTree<int, int>.Body<Op>(d.Count.Repeat(() => -1)); for (var i = 0; i < t; i++) { var (lo, ro) = sounds[i]; var l = d[lo]; var r = d[ro]; tree.Apply(l, r + 1, i + 1); } for (var i = 0; i < n; i++) { var x = d[xz[i]]; Out(tree.Product(x, x + 1)); } return null; } public static void Main() => new AtCoder().Run(); public void Run() { var res = Solve(); if (res != null) { if (res is bool yes) res = yes ? "Yes" : "No"; sw.WriteLine(res); } sw.Flush(); } string[] input = Array.Empty<string>(); int iter = 0; readonly StreamWriter sw = new(Console.OpenStandardOutput()) { AutoFlush = false }; #pragma warning disable IDE0051 string String() { while (iter >= input.Length) (input, iter) = (Console.ReadLine()!.Split(' '), 0); return input[iter++]; } T Input<T>() where T : IParsable<T> => T.Parse(String(), null); int Int() => Input<int>(); void Out(object? x, string? separator = null) { separator ??= Environment.NewLine; if (x is System.Collections.IEnumerable obj and not string) { var firstLine = true; foreach (var item in obj) { if (!firstLine) sw.Write(separator); firstLine = false; sw.Write(item); } } else sw.Write(x); sw.WriteLine(); } #pragma warning restore IDE0051 }