Submission #50257081

---

Source Code Expand

// -*- coding:utf-8-unix -*-
/*
このコード、と～おれ!
  ∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂    ノ       ・゜+.
 しーＪ       °。+ *´¨)
                  .· ´¸.·*´¨) ¸.·*¨)
                                      (¸.·´ (¸.·'* ☆
*/

#[allow(unused_imports)]
use ac_library::*;
use itertools::Itertools;
use proconio::input;
use proconio::marker::Chars;
use std::collections::{BinaryHeap, VecDeque};



static INF: usize = 1e18 as usize;

trait Vector<T> {
    fn insertion_sort(&mut self, elem: T);
    fn print_continuous(&self);
    fn print_space_separate(&self);
    fn print_linebreak(&self);
}

impl<T: std::cmp::Ord  + std::fmt::Display> Vector<T> for Vec<T> {
    fn insertion_sort(&mut self, elem: T) { let idx = self.binary_search(&elem).unwrap_or_else(|x| x); self.insert(idx, elem); }
    fn print_continuous(&self) { for i in 0..self.len() { print!("{}", self[i]); } println!() }
    fn print_space_separate(&self) { for i in 0..self.len() { print!("{}", self[i]); if i != self.len()-1 { print!(" ") } } println!() }
    fn print_linebreak(&self) { for i in 0..self.len() { println!("{}", self[i]); } }
}

use num_traits::{FromPrimitive, Num, NumCast};
struct BIT<T> {
    n: usize, // 配列の要素数
    bit: Vec<Vec<T>>, // データを持つ。1-indexedで、初期値は0となる。
}

impl<T> BIT<T> where T: Num + Clone + std::ops::Neg<Output = T> + NumCast + FromPrimitive {
    fn new(size: usize) -> BIT<T>{
        let v = vec![vec![T::zero(); size+1]; 2];
        BIT{ n: size+1, bit: v}
    }

    //[l, r)にxを追加
    fn add(&mut self, l: usize, r: usize, x: T) {
        self._add_sub(0, l, -x.clone() * NumCast::from(l - 1).unwrap());
        self._add_sub(0, r, x.clone() * NumCast::from(r - 1).unwrap());
        self._add_sub(1, l, x.clone());
        self._add_sub(1, r, -x.clone());
    }

    fn _add_sub(&mut self, p: usize, i: usize, x: T) {
        let mut idx = i;
        while idx < self.n {
            self.bit[p][idx] = self.bit[p][idx].clone() + x.clone();

            idx += (idx as isize & (idx as isize * -1)) as usize;
        }
    }

    fn sum(&self, i: usize) -> T { self._sum_sub(0, i) + self._sum_sub(1, i) * NumCast::from(i).unwrap() }

    fn _sum_sub(&self, p: usize, i: usize) -> T{
        let mut s :T = T::zero();
        let mut idx = i;
        while idx > 0 {
            s = s + self.bit[p][idx].clone();
            idx -= (idx as isize & (idx as isize * -1)) as usize;
        }
        s
    }

}

fn solve() {
    input! {
        n: usize,
        m: usize,
        a: [isize; n],
        b: [usize; m]
    }

    let mut bit = BIT::new(n);

    for i in 0..n {
        bit.add(i+1, i+2, a[i]);
    }


    for &x in &b {
        let v = bit.sum(x+1) - bit.sum(x);
        let kubaru = v / n as isize;
        bit.add(x+1, x+2, -v);
        bit.add(1, n+1, kubaru);

        let l = x+2;
        let r = (x + 1 + (v % n as isize) as usize) % n + 1;
        if l <= r {
            bit.add(l, r, 1);
        }else{
            bit.add(l, n+1, 1);
            bit.add(1, r, 1);
        }
    }

    for i in 0..n {
        if i != n-1 {
            print!("{} ", bit.sum(i+1) - bit.sum(i));
        }else{
           println!("{}", bit.sum(i+1) - bit.sum(i));
        }
    }

}

fn main() {
    // input! { i: usize }
    let mut i = 1;
    while i != 0 { solve(); i -= 1; }
}

Submission Info

Compile Error

warning: unused import: `itertools::Itertools`
  --> src/main.rs:14:5
   |
14 | use itertools::Itertools;
   |     ^^^^^^^^^^^^^^^^^^^^
   |
   = note: `#[warn(unused_imports)]` on by default

warning: unused import: `proconio::marker::Chars`
  --> src/main.rs:16:5
   |
16 | use proconio::marker::Chars;
   |     ^^^^^^^^^^^^^^^^^^^^^^^

warning: unused imports: `BinaryHeap`, `VecDeque`
  --> src/main.rs:17:24
   |
17 | use std::collections::{BinaryHeap, VecDeque};
   |                        ^^^^^^^^^^  ^^^^^^^^

warning: static `INF` is never used
  --> src/main.rs:21:8
   |
21 | static INF: usize = 1e18 as usize;
   |        ^^^
   |
   = note: `#[warn(dead_code)]` on by default

Judge Result