結果

問題 No.2395 区間二次変換一点取得
ユーザー kakel-sankakel-san
提出日時 2023-07-28 22:34:51
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 698 ms / 2,000 ms
コード長 3,798 bytes
コンパイル時間 2,103 ms
コンパイル使用メモリ 114,216 KB
実行使用メモリ 56,444 KB
最終ジャッジ日時 2024-10-06 19:58:51
合計ジャッジ時間 8,931 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
26,968 KB
testcase_01 AC 32 ms
25,048 KB
testcase_02 AC 32 ms
25,004 KB
testcase_03 AC 32 ms
25,288 KB
testcase_04 AC 32 ms
27,348 KB
testcase_05 AC 32 ms
25,176 KB
testcase_06 AC 32 ms
24,904 KB
testcase_07 AC 32 ms
25,036 KB
testcase_08 AC 32 ms
25,264 KB
testcase_09 AC 33 ms
25,292 KB
testcase_10 AC 33 ms
25,424 KB
testcase_11 AC 36 ms
23,048 KB
testcase_12 AC 83 ms
30,656 KB
testcase_13 AC 698 ms
56,304 KB
testcase_14 AC 688 ms
54,340 KB
testcase_15 AC 686 ms
54,208 KB
testcase_16 AC 691 ms
54,084 KB
testcase_17 AC 691 ms
54,412 KB
testcase_18 AC 432 ms
56,444 KB
testcase_19 AC 436 ms
56,316 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static int NN => int.Parse(ReadLine());
    static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
    static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var c = NList;
        var (n, b, q) = (c[0], c[1], (int)c[2]);
        var map = NArr(q);
        var x = new long[q + 1];
        var y = new long[q + 1];
        var z = new long[q + 1];
        x[0] = 1;
        y[0] = 1;
        z[0] = 1;
        var seg = new LazyAddSumSegmentTree(new int[n]);
        var ans = new string[q];
        for (var i = 0; i < q; ++i)
        {
            x[i + 1] = (x[i] + 1) % b;
            y[i + 1] = (3 * y[i] % b + 2 * x[i + 1] % b * z[i] % b) % b;
            z[i + 1] = 3 * z[i] % b;
            seg.AddRange(map[i][0] - 1, map[i][2], 1);
            var time = (int)seg.Get(map[i][1] - 1, map[i][1]);
            ans[i] = $"{x[time]} {y[time]} {z[time]}";
        }
        WriteLine(string.Join("\n", ans));
    }
    class LazyAddSumSegmentTree
    {
        public long[] tree;
        public long[] lazy;
        /// <summary>範囲外を参照したときの値 欲しい値の種類によって変える</summary>
        long INF = 0;
        int size;
        public LazyAddSumSegmentTree(int[] list)
        {
            size = 1;
            while (size < list.Length) size <<= 1;
            tree = Enumerable.Repeat(INF, size * 2).ToArray();
            lazy = Enumerable.Repeat(INF, size * 2).ToArray();
            for (var i = 0; i < list.Length; ++i) tree[i + size] = list[i];
            for (var i = size - 1; i >= 1; --i) tree[i] = Calc(tree[i * 2], tree[i * 2 + 1]);
        }
        /// <summary>取得時の評価 欲しい値の種類によって変える</summary>
        long Calc(long a, long b)
        {
            return a + b;
        }
        /// <summary>遅延評価の値を適用する 区間に対する操作によって変える</summary>
        long Leval(long tval, long lval)
        {
            return tval + lval;
        }
        void Eval(int k)
        {
            if (lazy[k] == INF) return;
            if (k < size)
            {
                lazy[k * 2] = Calc(lazy[k * 2], lazy[k] / 2);
                lazy[k * 2 + 1] = Calc(lazy[k * 2 + 1], lazy[k] / 2);
            }
            tree[k] = Leval(tree[k], lazy[k]);
            lazy[k] = INF;
        }
        /// <summary>区間加算(end is not include)</summary>
        public void AddRange(int begin, int end, long value, int k = 1, int l = 0, int r = -1)
        {
            if (r < 0) r = size;
            Eval(k);
            if (begin <= l && r <= end)
            {
                lazy[k] += (r - l) * value;
                Eval(k);
            }
            else if (begin < r && l < end)
            {
                AddRange(begin, end, value, k * 2, l, (l + r) / 2);
                AddRange(begin, end, value, k * 2 + 1, (l + r) / 2, r);
                tree[k] = Calc(tree[k * 2], tree[k * 2 + 1]);
            }
        }
        /// <summary>値の取得(end is not include)</summary>
        public long Get(int begin, int end, int k = 1, int l = 0, int r = -1)
        {
            if (r < 0) r = size;
            Eval(k);
            if (begin <= l && r <= end) return tree[k];
            else if (begin < r && l < end)
                return Calc(Get(begin, end, k * 2, l, (l + r) / 2), Get(begin, end, k * 2 + 1, (l + r) / 2, r));
            else return INF;
        }
    }
}
0