結果

問題 No.1000 Point Add and Array Add
ユーザー nehan_der_thalnehan_der_thal
提出日時 2020-03-01 02:31:18
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 3,681 bytes
コンパイル時間 1,105 ms
コンパイル使用メモリ 109,184 KB
実行使用メモリ 56,708 KB
最終ジャッジ日時 2024-04-21 22:01:12
合計ジャッジ時間 11,018 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
19,200 KB
testcase_01 AC 36 ms
19,072 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 37 ms
19,328 KB
testcase_05 AC 37 ms
18,816 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 927 ms
47,568 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Linq;
using System.IO;
using System.Collections.Generic;
using static System.Math;

class SegTree
{
  public long[] data;
  public long[] lazydata;
  private int num;
  private long ide_ele;
  private long F(long x, long y){
    return x > y ? x : y;
  }
  private int Pow(int x, int y){
    int r = 1;
    for (int i = 0; i < y; i++){
      r *= x;
    }
    return r;
  }
  private List<int> Gindices(int l, int r){
    List<int> R = new List<int>();
    l += num; r += num;
    int lm = (l / (l & -l))>>1;
    int rm = (r / (r & -r))>>1;
    //Console.WriteLine(rm);
    while (l < r){
      if (r <= rm){
        R.Add(r-1);
      }
      if (l <= lm){
        R.Add(l-1);
      }
      l >>= 1; r >>= 1;
    }
    while (l > 0){
      R.Add(l-1);
      l >>= 1;
    }
    return R;
  }

  private void Propagate(List<int> indices){
    foreach(int i in indices.AsEnumerable().Reverse()){
      long v = lazydata[i]; lazydata[i] = 0;
      if (v==0) continue;
      lazydata[2*i+1] += v; data[2*i+1] += v;
      lazydata[2*i+2] += v; data[2*i+2] += v;
    }
  }

  public void Update(int i, long x){
    i += num-1;
    data[i] = x;
    while (i>0){
      i = (i-1)>>1;
      data[i] = F(data[2*i+1], data[2*i+2]);
    }
  }
  public void UpdateRange(int l, int r, long x){
    //Console.WriteLine($"{l}, {r}");
    List<int> gindices = Gindices(l, r);
    l += num; r += num;
    while (l < r){
      if (l%2 == 1){
        lazydata[l-1] += x; data[l-1] += x; l++;
      }
      if (r%2 == 1){
        r--; lazydata[r-1] += x; data[r-1] += x;
      }
      l >>= 1; r >>= 1;
    }
    foreach(int i in gindices){
      //Console.WriteLine(i);
      data[i] = F(data[2*i+1], data[2*i+2]) + lazydata[i];
    }
  }
  public long Query(int l, int r){
    Propagate(Gindices(l, r));
    l += num; r += num;
    long R = ide_ele;
    while (l < r){
      //Console.WriteLine($"Q {l-1} {r-2}");
      if (l%2 == 1){
        R = F(R, data[l-1]); l++;
      }
      if (r%2 == 1){
        r--; R = F(R, data[r-1]);
      }
      l >>= 1; r >>= 1;
    }
    return R;
  }
  public SegTree(long[] values, long ide_ele)
  {
    int N = values.Length;
    this.ide_ele = ide_ele;
    int tmp = N+1; // 遅延操作のため1段多く作る
    int r = 0;
    while (tmp > 0){
      tmp >>= 1;
      r++;
    }
    num = Pow(2, r);
    data = new long[2*num];
    lazydata = new long[2*num];
    for (int i = 0; i < N; i++){
      data[i+num-1] = values[i];
    }
    for (int i = num - 2; i >= 0; i--){
      data[i] = F(data[2*i+1], data[2*i+2]);
    }
  }
}

class P
{
  static int[] Input(){
    return Console.ReadLine().Split().Select(int.Parse).ToArray();
  }
  static int[][] Input2(int n){
    int[][] X = new int[n][];
    for(int i = 0; i < n; i++){
      X[i] = Input();
    }
    return X;
  }
  static void Main()
  {
    int[] NQ = Input();
    int[] A = Input();

    var ql = new List<(string type, int x, int y)>();
    for(int i=0;i<NQ[0];i++){
      ql.Add(("A", i, A[i]));
    }
    for(int i=0;i<NQ[1];i++){
      string[] cxy = Console.ReadLine().Split();
      int xx = int.Parse(cxy[1]);
      int yy = int.Parse(cxy[2]);
      ql.Add((cxy[0], xx-1, yy));
    }
    SegTree x = new SegTree(new long[NQ[0]], -long.MaxValue);
    var B = new long[NQ[0]];
    for(int i=NQ[1]-1+NQ[0];i>=0;i--){
      var qi = ql[i];
      if(qi.type == "A"){
        B[qi.x] += qi.y * (int)x.Query(qi.x, qi.x+1);
      }else{
        x.UpdateRange(qi.x, qi.y, 1);
      }
    }
    var sw = new StreamWriter(Console.OpenStandardOutput()){AutoFlush = false};
    Console.SetOut(sw);
    Console.WriteLine(string.Join(" ", B));
    Console.Out.Flush();
  }
}
0