#682665 (Rust) No.1623 三角形の制作

提出ソース

結果

問題	No.1623 三角形の制作
ユーザー	akiradeveloper
提出日時	2021-07-23 21:55:22
言語	Rust (1.77.0)
結果	AC
実行時間	80 ms / 2,000 ms
コード長	9,170 bytes
コンパイル時間	4,268 ms
コンパイル使用メモリ	164,360 KB
実行使用メモリ	9,060 KB
最終ジャッジ日時	2023-09-25 21:54:27
合計ジャッジ時間	5,964 ms
ジャッジサーバーID （参考情報）	judge11 / judge13

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	13 ms 4,380 KB
testcase_01	AC	13 ms 4,376 KB
testcase_02	AC	51 ms 5,060 KB
testcase_03	AC	48 ms 4,888 KB
testcase_04	AC	48 ms 4,900 KB
testcase_05	AC	80 ms 6,780 KB
testcase_06	AC	22 ms 4,384 KB
testcase_07	AC	49 ms 4,984 KB
testcase_08	AC	23 ms 4,380 KB
testcase_09	AC	46 ms 4,604 KB
testcase_10	AC	67 ms 6,128 KB
testcase_11	AC	55 ms 5,260 KB
testcase_12	AC	20 ms 4,404 KB
testcase_13	AC	22 ms 5,036 KB
testcase_14	AC	21 ms 4,940 KB
testcase_15	AC	34 ms 8,952 KB
testcase_16	AC	35 ms 9,008 KB
testcase_17	AC	35 ms 9,060 KB
testcase_18	AC	35 ms 6,936 KB
testcase_19	AC	23 ms 5,580 KB
testcase_20	AC	13 ms 4,380 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

warning: unused variable: `out`
   --> Main.rs:113:13
    |
113 |     let mut out = BufWriter::new(out.lock());
    |             ^^^ help: if this is intentional, prefix it with an underscore: `_out`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: variable does not need to be mutable
   --> Main.rs:113:9
    |
113 |     let mut out = BufWriter::new(out.lock());
    |         ----^^^
    |         |
    |         help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: associated function `add` is never used
   --> Main.rs:173:12
    |
173 |     pub fn add(&mut self, i: usize, x: i64) {
    |            ^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: 3 warnings emitted

ソースコード

raw source code

#[doc = " https://github.com/akiradeveloper/rust-comp-snippets"]
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::iter::FromIterator;
#[macro_export]
macro_rules ! chmax { ( $ x : expr , $ ( $ v : expr ) ,+ ) => { $ ( $ x = std :: cmp :: max ( $ x ,$ v ) ; ) + } ; }
#[macro_export]
macro_rules ! chmin { ( $ x : expr , $ ( $ v : expr ) ,+ ) => { $ ( $ x = std :: cmp :: min ( $ x ,$ v ) ; ) + } ; }
#[macro_export]
macro_rules ! max { ( $ x : expr ) => ( $ x ) ; ( $ x : expr , $ ( $ xs : expr ) ,+ ) => { std :: cmp :: max ( $ x , max ! ( $ ( $ xs ) ,+ ) ) } ; }
#[macro_export]
macro_rules ! min { ( $ x : expr ) => ( $ x ) ; ( $ x : expr , $ ( $ xs : expr ) ,+ ) => { std :: cmp :: min ( $ x , min ! ( $ ( $ xs ) ,+ ) ) } ; }
#[macro_export]
macro_rules ! dvec { ( $ t : expr ; $ len : expr ) => { vec ! [ $ t ; $ len ] } ; ( $ t : expr ; $ len : expr , $ ( $ rest : expr ) ,* ) => { vec ! [ dvec ! ( $ t ; $ ( $ rest ) ,* ) ; $ len ] } ; }
#[macro_export]
macro_rules ! cfor { ( ; $ ( $ rest : tt ) * ) => { cfor ! ( ( ) ; $ ( $ rest ) * ) } ; ( $ ( $ init : stmt ) ,+; ; $ ( $ rest : tt ) * ) => { cfor ! ( $ ( $ init ) ,+; ! false ; $ ( $ rest ) * ) } ; ( $ ( $ init : stmt ) ,+; $ cond : expr ; ; $ body : block ) => { cfor ! { $ ( $ init ) ,+; $ cond ; ( ) ; $ body } } ; ( $ ( $ init : stmt ) ,+; $ cond : expr ; $ ( $ step : expr ) ,+; $ body : block ) => { { $ ( $ init ; ) + while $ cond { let mut _first = true ; let mut _continue = false ; loop { if ! _first { _continue = true ; break } _first = false ; $ body } if ! _continue { break } $ ( $ step ; ) + } } } ; }
#[doc = " main"]
#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};
#[macro_export]
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut parser = Parser :: from_str ( $ s ) ; input_inner ! { parser , $ ( $ r ) * } } ; ( parser = $ parser : ident , $ ( $ r : tt ) * ) => { input_inner ! { $ parser , $ ( $ r ) * } } ; ( new_stdin_parser = $ parser : ident , $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let reader = std :: io :: BufReader :: new ( stdin . lock ( ) ) ; let mut $ parser = Parser :: new ( reader ) ; input_inner ! { $ parser , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { input ! { new_stdin_parser = parser , $ ( $ r ) * } } ; }
#[macro_export]
macro_rules ! input_inner { ( $ parser : ident ) => { } ; ( $ parser : ident , ) => { } ; ( $ parser : ident , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ parser , $ t ) ; input_inner ! { $ parser $ ( $ r ) * } } ; }
#[macro_export]
macro_rules ! read_value { ( $ parser : ident , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ parser , $ t ) ) ,* ) } ; ( $ parser : ident , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ parser , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ parser : ident , chars ) => { read_value ! ( $ parser , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ parser : ident , usize1 ) => { read_value ! ( $ parser , usize ) - 1 } ; ( $ parser : ident , $ t : ty ) => { $ parser . next ::<$ t > ( ) . expect ( "Parse error" ) } ; }
use std::io;
use std::io::BufRead;
use std::str;
pub struct Parser<R> {
    reader: R,
    buf: Vec<u8>,
    pos: usize,
}
impl Parser<io::Empty> {
    pub fn from_str(s: &str) -> Parser<io::Empty> {
	Parser {
	    reader: io::empty(),
	    buf: s.as_bytes().to_vec(),
	    pos: 0,
	}
    }
}
impl<R: BufRead> Parser<R> {
    pub fn new(reader: R) -> Parser<R> {
	Parser {
	    reader: reader,
	    buf: vec![],
	    pos: 0,
	}
    }
    pub fn update_buf(&mut self) {
	self.buf.clear();
	self.pos = 0;
	loop {
	    let (len, complete) = {
		let buf2 = self.reader.fill_buf().unwrap();
		self.buf.extend_from_slice(buf2);
		let len = buf2.len();
		if len == 0 {
		    break;
		}
		(len, buf2[len - 1] <= 0x20)
	    };
	    self.reader.consume(len);
	    if complete {
		break;
	    }
	}
    }
    pub fn next<T: str::FromStr>(&mut self) -> Result<T, T::Err> {
	loop {
	    let mut begin = self.pos;
	    while begin < self.buf.len() && (self.buf[begin] <= 0x20) {
		begin += 1;
	    }
	    let mut end = begin;
	    while end < self.buf.len() && (self.buf[end] > 0x20) {
		end += 1;
	    }
	    if begin != self.buf.len() {
		self.pos = end;
		return str::from_utf8(&self.buf[begin..end]).unwrap().parse::<T>();
	    } else {
		self.update_buf();
	    }
	}
    }
}
#[allow(unused_macros)]
macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) ; } }
#[doc = " https://github.com/hatoo/competitive-rust-snippets"]
const BIG_STACK_SIZE: bool = true;
#[allow(dead_code)]
fn main() {
    use std::thread;
    if BIG_STACK_SIZE {
	thread::Builder::new()
	    .stack_size(32 * 1024 * 1024)
	    .name("solve".into())
	    .spawn(solve)
	    .unwrap()
	    .join()
	    .unwrap();
    } else {
	solve();
    }
}
fn solve() {
    let out = stdout();
    let mut out = BufWriter::new(out.lock());
    input!{
        n:usize,
        r:[i64;n],
        g:[i64;n],
        b:[i64;n],
    }
    let mut r=r;
    r.sort();

    let mut g=g;
    g.sort();
    let mut gcnt_=vec![0;10000];
    for &x in &g {
        gcnt_[x as usize]+=1;
    }
    let gcnt=CumSum1::from_vec(gcnt_.clone());

    let mut b=b;
    b.sort();
    let mut bcnt_=vec![0;10000];
    for &x in &b {
        bcnt_[x as usize]+=1;
    }
    let bcnt=CumSum1::from_vec(bcnt_.clone());

    let gbcnt = multiply(&gcnt_, &bcnt_);
    let gbcnt = CumSum1::from_vec(gbcnt);
    let mut ans = 0;
    for &x in &r {
        // dbg!(x);
        let g=gcnt.query(0, (x+1) as usize);
        // dbg!(g);
        let b=bcnt.query(0, (x+1) as usize);
        // dbg!(b);
        ans += g*b;
        ans -= gbcnt.query(0, (x+1) as usize);
    }
    println!("{}",ans);
}
struct CumSum1 {
    base: Vec<i64>,
    dp: Vec<i64>,
}
impl CumSum1 {
    pub fn new(n: usize) -> Self {
        CumSum1 {
            base: vec![0; n],
            dp: vec![],
        }
    }
    pub fn from_vec(a: Vec<i64>) -> Self {
        let n = a.len();
        let mut x = Self::new(n);
        for i in 0..n {
            x.set(i, a[i]);
        }
        x.build();
        x
    }
    pub fn add(&mut self, i: usize, x: i64) {
        self.base[i] += x;
    }
    pub fn set(&mut self, i: usize, x: i64) {
        self.base[i] = x;
    }
    pub fn build(&mut self) {
        let n = self.base.len();
        let mut dp = vec![0; n + 1];
        let mut acc = 0;
        for i in 0..n {
            acc += self.base[i];
            dp[i + 1] = acc;
        }
        self.dp = dp;
    }
    #[doc = "[i,j)"]
    pub fn query(&self, i: usize, j: usize) -> i64 {
        self.dp[j] - self.dp[i]
    }
}
fn karatsuba<T>(a: &[T], b: &[T], c: &mut [T])
where
    T: std::marker::Copy
        + std::ops::Add<Output = T>
        + std::ops::Sub<Output = T>
        + std::ops::Mul<Output = T>
        + std::default::Default,
{
    let n = a.len();
    if n <= 32 {
        for (i, a) in a.iter().enumerate() {
            for (c, b) in c[i..].iter_mut().zip(b.iter()) {
                *c = *c + *a * *b;
            }
        }
        return;
    }
    if n & 1 == 1 {
        karatsuba(&a[1..], &b[1..], &mut c[2..]);
        let x = a[0];
        let y = b[0];
        c[0] = c[0] + x * y;
        for (c, (a, b)) in c[1..].iter_mut().zip(a[1..].iter().zip(b[1..].iter())) {
            *c = *c + x * *b + *a * y;
        }
        return;
    }
    let m = n / 2;
    karatsuba(&a[..m], &b[..m], &mut c[..n]);
    karatsuba(&a[m..], &b[m..], &mut c[n..]);
    let mut buf = vec![T::default(); 2 * n];
    let (x, y) = buf.split_at_mut(m);
    let (y, z) = y.split_at_mut(m);
    for (x, (p, q)) in x.iter_mut().zip(a.iter().zip(a[m..].iter())) {
        *x = *p + *q;
    }
    for (y, (p, q)) in y.iter_mut().zip(b.iter().zip(b[m..].iter())) {
        *y = *p + *q;
    }
    karatsuba(x, y, z);
    for (z, (p, q)) in z.iter_mut().zip(c[..n].iter().zip(c[n..].iter())) {
        *z = *z - (*p + *q);
    }
    for (c, z) in c[m..].iter_mut().zip(z.iter()) {
        *c = *c + *z;
    }
}
pub fn multiply<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: std::marker::Copy
        + std::ops::Add<Output = T>
        + std::ops::Sub<Output = T>
        + std::ops::Mul<Output = T>
        + std::default::Default,
{
    let mut i = 0;
    let mut j = 0;
    let mut ans = vec![T::default(); a.len() + b.len()];
    let mut c = Vec::with_capacity(a.len() + b.len());
    while i < a.len() && j < b.len() {
        let x = a.len() - i;
        let y = b.len() - j;
        let z = std::cmp::min(x, y);
        c.clear();
        c.resize(2 * z, T::default());
        karatsuba(&a[i..(i + z)], &b[j..(j + z)], &mut c);
        for (ans, c) in ans[(i + j)..].iter_mut().zip(c.iter()) {
            *ans = *ans + *c;
        }
        if x <= y {
            j += x;
        } else {
            i += y;
        }
    }
    ans.truncate(a.len() + b.len() - 1);
    ans
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード