結果

問題 No.631 Noelちゃんと電車旅行
ユーザー EmKjpEmKjp
提出日時 2019-05-12 17:31:14
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 1,111 ms / 2,000 ms
コード長 8,034 bytes
コンパイル時間 1,225 ms
コンパイル使用メモリ 120,464 KB
実行使用メモリ 54,144 KB
最終ジャッジ日時 2024-04-10 07:57:55
合計ジャッジ時間 15,769 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 815 ms
29,416 KB
testcase_01 AC 1,105 ms
51,456 KB
testcase_02 AC 1,026 ms
53,448 KB
testcase_03 AC 1,029 ms
54,144 KB
testcase_04 AC 1,111 ms
54,016 KB
testcase_05 AC 1,093 ms
53,468 KB
testcase_06 AC 436 ms
38,456 KB
testcase_07 AC 222 ms
43,312 KB
testcase_08 AC 785 ms
48,740 KB
testcase_09 AC 978 ms
42,588 KB
testcase_10 AC 630 ms
48,272 KB
testcase_11 AC 562 ms
44,556 KB
testcase_12 AC 747 ms
48,652 KB
testcase_13 AC 719 ms
37,040 KB
testcase_14 AC 355 ms
30,468 KB
testcase_15 AC 587 ms
38,508 KB
testcase_16 AC 31 ms
25,432 KB
testcase_17 AC 31 ms
27,272 KB
testcase_18 AC 31 ms
25,336 KB
testcase_19 AC 32 ms
27,404 KB
testcase_20 AC 31 ms
25,364 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 System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;

partial class Solver
{
    public void Run()
    {
        var N = ni();
        var T = ni(N - 1);
        var M = ni();
        var L = new int[M];
        var R = new int[M];
        var D = new int[M];
        for (int i = 0; i < M; i++)
        {
            L[i] = ni(); R[i] = ni(); D[i] = ni();
        }
        // Max(0, D[i] - 3 * (i - 1));

        var tree = new LazyRangeAddSegmentTree();

        tree.Build(Enumerable.Range(0, N - 1)
            .Select(i => new NodeValue { Index = i, Delay = T[i] })
            .ToArray());

        for (int i = 0; i < M; i++)
        {
            var l = L[i] - 1;
            var r = R[i] - 1;
            tree.RangeAdd(l, r + 1, D[i]);
            var maxWaitTime = tree.Query(0, N - 1).WaitTime;
            cout.WriteLine(maxWaitTime + 3 * (N - 1));
        }
    }

}

public struct NodeValue
{
    public int Index;
    public long Delay;
    public long WaitTime => Math.Max(0, Delay - 3 * (Index));

    public static NodeValue Merge(NodeValue v1, NodeValue v2)
    {
        if (v1.WaitTime < v2.WaitTime)
        {
            return v2;
        }
        else
        {
            return v1;
        }
    }
}
public class LazyRangeAddSegmentTree : LazySegmentTree<NodeValue>
{
    private long[] lazyAdded;

    public LazyRangeAddSegmentTree()
    {
    }

    protected override void InitializeLazyParameters()
    {
        lazyAdded = new long[node.Length];
    }

    protected override NodeValue Merge(NodeValue v1, NodeValue v2)
    {
        if (v1.WaitTime < v2.WaitTime)
        {
            return v2;
        }
        else
        {
            return v1;
        }
    }

    protected override void LazyPropagate(int k, int l, int r)
    {
        if (lazyAdded[k] == 0) return;

        var current = node[k].Value;

        current.Delay += lazyAdded[k];

        if (k < N - 1)
        {
            lazyAdded[Left(k)] += lazyAdded[k];
            lazyAdded[Right(k)] += lazyAdded[k];
        }

        lazyAdded[k] = 0;
        node[k] = current;
    }

    public void RangeAdd(int begin, int end, int value)
    {
        LazyUpdate((int i, int v) => lazyAdded[i] += v, begin, end, value);
    }
}

public abstract class LazySegmentTree<TNodeValue> : SegmentTree<TNodeValue> where TNodeValue : struct
{
    public override void Build(int _n, Func<int, TNodeValue> create)
    {
        base.Build(_n, create);
        InitializeLazyParameters();
    }

    virtual protected void InitializeLazyParameters()
    {
    }

    protected override TNodeValue? Query(int begin, int end, int k, int l, int r)
    {
        LazyPropagate(k, l, r);
        return base.Query(begin, end, k, l, r);
    }

    abstract protected void LazyPropagate(int k, int l, int r);

    private void LazyUpdate<T>(Action<int, T> update,
        int begin, int end, T value, int k, int l, int r)
    {
        if (r <= begin || end <= l)
        {
            LazyPropagate(k, l, r);
            return;
        }
        if (begin <= l && r <= end)
        {
            update(k, value);
            LazyPropagate(k, l, r);
            return;
        }
        LazyPropagate(k, l, r);
        int mid = (l + r) / 2;
        LazyUpdate(update, begin, end, value, Left(k), l, mid);
        LazyUpdate(update, begin, end, value, Right(k), mid, r);
        node[k] = Merge(node[Left(k)], node[Right(k)]);
    }

    protected void LazyUpdate<T>(Action<int, T> update, int begin, int end, T value)
    {
        LazyUpdate(update, begin, end, value, 0, 0, N);
    }
}
public abstract class SegmentTree<TNodeValue> where TNodeValue : struct
{
    protected int N { get; private set; }
    protected TNodeValue?[] node;
    protected static int Left(int p) { return p * 2 + 1; }
    protected static int Right(int p) { return p * 2 + 2; }

    public SegmentTree() { }

    public void Build(IList<TNodeValue> array)
    {
        Build(array.Count, i => array[i]);
    }

    virtual public void Build(int _n, Func<int, TNodeValue> create)
    {
        N = 1;
        while (N < _n) N *= 2;
        node = new TNodeValue?[2 * N];

        for (int i = 0; i < _n; i++) node[i + N - 1] = create(i);
        for (int i = N - 2; i >= 0; i--) node[i] = Merge(node[Left(i)], node[Right(i)]);
    }

    protected TNodeValue? Merge(TNodeValue? left, TNodeValue? right)
    {
        if (left != null && right != null) return Merge(left.Value, right.Value);
        if (left == null) return right;
        if (right == null) return left;
        return null;
    }

    protected abstract TNodeValue Merge(TNodeValue left, TNodeValue right);

    public void Update(int index, TNodeValue val)
    {
        int p = index + N - 1;
        node[p] = val;
        while (p > 0)
        {
            p = (p - 1) / 2;
            node[p] = Merge(node[Left(p)], node[Right(p)]);
        }
    }

    protected virtual TNodeValue? Query(int begin, int end, int k, int l, int r)
    {
        if (r <= begin || end <= l) return null;
        if (begin <= l && r <= end) return node[k];
        int mid = (l + r) / 2;
        return Merge(
            Query(begin, end, Left(k), l, mid),
            Query(begin, end, Right(k), mid, r)
        );
    }

    public TNodeValue Query(int begin, int end)
    {
        return Query(begin, end, 0, 0, N).Value;
    }
};


// PREWRITEN CODE BEGINS FROM HERE
partial class Solver : Scanner
{
    public static void Main(string[] args)
    {
        new Solver(Console.In, Console.Out).Run();
    }

    TextReader cin;
    TextWriter cout;

    public Solver(TextReader reader, TextWriter writer)
        : base(reader)
    {
        this.cin = reader;
        this.cout = writer;
    }
    public Solver(string input, TextWriter writer)
        : this(new StringReader(input), writer)
    {
    }

    public int ni() { return NextInt(); }
    public int[] ni(int n) { return NextIntArray(n); }
    public long nl() { return NextLong(); }
    public long[] nl(int n) { return NextLongArray(n); }
    public double nd() { return NextDouble(); }
    public string ns() { return Next(); }
    public string[] ns(int n) { return NextArray(n); }
}

public class Scanner
{
    private TextReader Reader;
    private Queue<String> TokenQueue = new Queue<string>();
    private CultureInfo ci = CultureInfo.InvariantCulture;

    public Scanner()
        : this(Console.In)
    {
    }

    public Scanner(TextReader reader)
    {
        this.Reader = reader;
    }

    public int NextInt() { return Int32.Parse(Next(), ci); }
    public long NextLong() { return Int64.Parse(Next(), ci); }
    public double NextDouble() { return double.Parse(Next(), ci); }
    public string[] NextArray(int size)
    {
        var array = new string[size];
        for (int i = 0; i < size; i++) array[i] = Next();
        return array;
    }
    public int[] NextIntArray(int size)
    {
        var array = new int[size];
        for (int i = 0; i < size; i++) array[i] = NextInt();
        return array;
    }

    public long[] NextLongArray(int size)
    {
        var array = new long[size];
        for (int i = 0; i < size; i++) array[i] = NextLong();
        return array;
    }

    public String Next()
    {
        if (TokenQueue.Count == 0)
        {
            if (!StockTokens()) throw new InvalidOperationException();
        }
        return TokenQueue.Dequeue();
    }

    public bool HasNext()
    {
        if (TokenQueue.Count > 0)
            return true;
        return StockTokens();
    }

    private bool StockTokens()
    {
        while (true)
        {
            var line = Reader.ReadLine();
            if (line == null) return false;
            var tokens = line.Trim().Split(" ".ToCharArray(), StringSplitOptions.RemoveEmptyEntries);
            if (tokens.Length == 0) continue;
            foreach (var token in tokens)
                TokenQueue.Enqueue(token);
            return true;
        }
    }
}
0