結果

問題 No.1000 Point Add and Array Add
コンテスト
ユーザー nehan_der_thal
提出日時 2020-03-01 02:32:54
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 830 ms / 2,000 ms
コード長 3,676 bytes
コンパイル時間 973 ms
コンパイル使用メモリ 115,036 KB
実行使用メモリ 60,056 KB
最終ジャッジ日時 2024-10-13 20:25:33
合計ジャッジ時間 9,026 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 * 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