結果

問題 No.3565 Take from Excluded
コンテスト
ユーザー tobisatis
提出日時 2026-06-05 23:34:18
言語 C#
(.NET 10.0.201)
コンパイル:
dotnet_c
実行:
/usr/bin/dotnet_wrap
結果
WA  
実行時間 -
コード長 2,389 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 14,779 ms
コンパイル使用メモリ 172,440 KB
実行使用メモリ 48,640 KB
最終ジャッジ日時 2026-06-05 23:35:16
合計ジャッジ時間 12,029 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9 WA * 1 TLE * 1 -- * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (96 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

diff #
raw source code 

#nullable enable

#region
var (_input, _iter) = (Array.Empty<string>(), 0);
T I<T>() where T : IParsable<T>
{
    while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Trim().Split(' '), 0);
    return T.Parse(_input[_iter++], null);
}
#endregion

static T[] Range<T>(int n, Func<T> F) => Enumerable.Range(0, n).Select(_ => F()).ToArray();

const int Mod = 998244353;

var n = I<int>();
var q = I<int>();
var az = Range(n, I<int>);
var qz = Range(q, () => (I<int>(), I<int>() - 1, I<int>()));

if (n > 3000 || q > 3000) throw new Exception();

az = az.Order().Distinct().ToArray();
long min = az[0];
n = az.Length;
var bz = new List<long>();
{
    var last = long.MinValue;
    var len = 1;
    foreach (var a in az)
    {
        if (a == last + 1)
        {
            len++;
            last = a;
            continue;
        }
        if (last >= 0)
        {
            bz.Add(len);
            bz.Add(a - last - 1);
        }
        len = 1;
        last = a;
    }
    bz.Add(len);
}

var (l0, l1) = (0L, 0L);
for (var i = 0; i < bz.Count; i++)
{
    var l = bz[i];
    if (i % 2 == 0) l0 += l;
    else l1 += l;
}

long At(long j)
{
    var res = min;
    var f = true;
    foreach (var l in bz)
    {
        if (f)
        {
            if (j < l) break;
            j -= l;
        }
        res = (res + l) % Mod;
        f = !f;
    }
    return res + j;
}

void O(long m)
{
    var b0 = bz[0];
    min = (min + b0) % Mod;
    l0 -= b0;
    bz = bz[1..];
    (l0, l1) = (l1, l0);
    if (l0 == m) return;
    if (l0 < m)
    {
        bz.Add(m - l0);
        l0 = m;
        return;
    }
    l0 = m;
    var f = true;
    var j = 0;
    l1 = 0;
    for (var i = 0; i < bz.Count; i++)
    {
        var l = bz[i];
        if (f)
        {
            if (l > m) break;
            m -= l;
        }
        else l1 += l;
        f = !f;
        j++;
    }
    bz = bz[..j];
    if (m > 0) bz.Add(m);
}

void OR(int k, int m)
{
    while (k > 0)
    {
        var u = bz.Count + 1;
        var t = k / u;
        if (t == 0 || l0 != m || l1 > m)
        {
            O(m);
            k--;
            continue;
        }
        min = (min + (long)t * m * 2) % Mod;
        k -= t * u;
    }
}

var ans = new List<long>();
foreach (var (k, j, m) in qz)
{
    OR(k, m);
    ans.Add(At(j) % Mod);
}
Console.WriteLine(string.Join(Environment.NewLine, ans));
0