結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー tobisatis
提出日時 2025-09-06 14:15:22
言語 C#
(.NET 8.0.404)
結果
WA  
実行時間 -
コード長 2,496 bytes
コンパイル時間 12,812 ms
コンパイル使用メモリ 170,320 KB
実行使用メモリ 250,160 KB
最終ジャッジ日時 2025-09-06 14:16:10
合計ジャッジ時間 27,778 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 3
other WA * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (109 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

#nullable enable

using System.Numerics;

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

var n = I<int>();
var m = I<int>();
var dataS = new PointAddRangeSum<long>(m);
var dataC = new RangeAddPointGet<int>(m);
var iwiz = new (int, long, int, int)[n];
for (var i = 0; i < n; i++)
{
    var a = I<int>();
    var l = I<int>() - 1;
    var r = I<int>();
    dataS.Add(i, a);
    dataC.Add(l, r, 1);
    iwiz[i] = (i, a, l, r);
}
var s = 0L;
for (var i = 0; i < n; i++)
{
    var (_, a, l, r) = iwiz[i];
    s += a * (r - l) - dataS.Sum(l, r);
}
var q = I<int>();
var ans = new long[q];
for (var i = 0; i < q; i++)
{
    var x = I<int>() - 1;
    var y = I<int>() - 1;
    var nl = I<int>() - 1;
    var nr = I<int>();
    var (t, a, l, r) = iwiz[x];
    s -= a * (r - l) - dataS.Sum(l, r);
    dataS.Add(t, -a);
    dataS.Add(y, a);
    s += a * (nr - nl) - dataS.Sum(nl, nr);
    dataC.Add(l, r, -1);
    s += a * dataC.Get(t);
    dataC.Add(nl, nr, 1);
    s -= a * dataC.Get(y);
    iwiz[x] = (y, a, nl, nr);
    ans[i] = s;
}
Console.WriteLine(string.Join(Environment.NewLine, ans));

class FenwickTree<T> where T : INumber<T>
{
    readonly T[] _values;
    public FenwickTree(int length) { _values = new T[length + 2]; }
    public void Add(int i, T value)
    {
        var values = _values;
        while (i < values.Length)
        {
            values[i] += value;
            i += i & -i;
        }
    }
    public T Sum(int i)
    {
        var values = _values;
        var res = T.Zero;
        while (i > 0)
        {
            res += values[i];
            i -= i & -i;
        }
        return res;
    }
}

class PointAddRangeSum<T> where T : INumber<T>
{
    public PointAddRangeSum(int length) { _data = new FenwickTree<T>(length); }
    public void Add(int at, T value) => _data.Add(at + 1, value);
    public T Sum(int l, int r) => _data.Sum(r) - _data.Sum(l); // [l, r)
    readonly FenwickTree<T>_data;
}

class RangeAddPointGet<T> where T : INumber<T>
{
    public RangeAddPointGet(int length) { _data = new FenwickTree<T>(length); }
    public void Add(int l, int r, T value) // [l, r)
    {
        _data.Add(l + 1, value);
        _data.Add(r + 1, -value);
    }
    public T Get(int at) => _data.Sum(at + 1);
    readonly FenwickTree<T>_data;
}
0