結果

問題 No.1209 XOR Into You
ユーザー ikd
提出日時 2020-09-02 22:40:41
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 4,379 bytes
コンパイル時間 18,534 ms
コンパイル使用メモリ 379,708 KB
実行使用メモリ 15,360 KB
最終ジャッジ日時 2024-11-21 23:42:48
合計ジャッジ時間 22,064 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 36 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

pub struct ProconReader<R: std::io::Read> {
    reader: R,
}

impl<R: std::io::Read> ProconReader<R> {
    pub fn new(reader: R) -> Self {
        Self { reader }
    }
    pub fn get<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .reader
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&byte| byte == b' ' || byte == b'\n' || byte == b'\r')
            .take_while(|&byte| byte != b' ' && byte != b'\n' && byte != b'\r')
            .collect::<Vec<_>>();
        std::str::from_utf8(&buf)
            .unwrap()
            .parse()
            .ok()
            .expect("Parse Error.")
    }
}

pub struct FenwickTree {
    n: usize,
    dat: Vec<i64>,
}

impl FenwickTree {
    pub fn new(n: usize) -> Self {
        let n = n.next_power_of_two();
        Self {
            n,
            dat: vec![0; n + 1],
        }
    }
    pub fn add(&mut self, k: usize, x: i64) {
        assert!(1 <= k && k <= self.n);
        let n = self.n as i32;
        let mut k = k as i32;
        while k <= n {
            self.dat[k as usize] += x;
            k += k & (-k);
        }
    }
    pub fn _sum(&self, r: usize) -> i64 {
        assert!(r <= self.n);
        let mut result = 0;
        let mut k = r as i32;
        while k >= 1 {
            result += self.dat[k as usize];
            k -= k & (-k);
        }
        result
    }
    pub fn sum(&self, l: usize, r: usize) -> i64 {
        if l > r {
            return 0;
        }
        assert!(1 <= l && l <= self.n);
        assert!(1 <= r && r <= self.n);
        self._sum(r) - self._sum(l - 1)
    }
}

mod binary_search {
    use std::ops::Range;
    pub trait BinarySearch<T> {
        fn lower_bound(&self, x: &T) -> usize;
        fn upper_bound(&self, x: &T) -> usize;
        fn split_by(&self, x: &T) -> (Range<usize>, Range<usize>, Range<usize>);
    }

    // min index self[i] >= x
    // that is, any j (j < i) holds self[j] < x
    impl<T: Ord> BinarySearch<T> for [T] {
        fn lower_bound(&self, x: &T) -> usize {
            if self[0] >= *x {
                return 0;
            }
            let mut lf = 0;
            let mut rg = self.len();
            // self[lf] < x
            while rg - lf > 1 {
                let md = (rg + lf) / 2;
                if self[md] < *x {
                    lf = md;
                } else {
                    rg = md;
                }
            }
            rg
        }

        // min index self[i] > x
        // that is, any j (j < i) holds self[j] <= x
        fn upper_bound(&self, x: &T) -> usize {
            if self[0] > *x {
                return 0;
            }
            let mut lf = 0;
            let mut rg = self.len();
            // self[lf] <= x
            while rg - lf > 1 {
                let md = (rg + lf) / 2;
                if self[md] <= *x {
                    lf = md;
                } else {
                    rg = md;
                }
            }
            rg
        }

        fn split_by(&self, x: &T) -> (Range<usize>, Range<usize>, Range<usize>) {
            let i = self.lower_bound(x);
            let j = self.upper_bound(x);
            (0..i, i..j, j..self.len())
        }
    }
}

use binary_search::BinarySearch;

fn main() {
    let stdin = std::io::stdin();
    let mut rd = ProconReader::new(stdin.lock());

    let n: usize = rd.get();
    let a: Vec<i64> = (0..n).map(|_| rd.get()).collect();
    let b: Vec<i64> = (0..n).map(|_| rd.get()).collect();

    let a = a.windows(2).map(|w| w[0] ^ w[1]).collect::<Vec<_>>();
    let b = b.windows(2).map(|w| w[0] ^ w[1]).collect::<Vec<_>>();

    let mut c = a.clone();
    c.sort();
    let mut d = b.clone();
    d.sort();
    if c.iter().zip(&d).any(|(cc, dd)| cc != dd) {
        println!("-1");
        return;
    }
    c.dedup();
    let idx = |x: i64| c.lower_bound(&x);
    let m = c.len();
    let mut ques = vec![std::collections::VecDeque::new(); m];
    for (i, &x) in a.iter().enumerate() {
        ques[idx(x)].push_back(i);
    }
    let mut fen = FenwickTree::new(n - 1);
    for i in 1..=(n - 1) {
        fen.add(i, 1);
    }
    let mut ans = 0;
    for x in b {
        let i = ques[idx(x)].pop_front().unwrap();
        ans += fen.sum(1, i);
        fen.add(i + 1, -1);
    }
    println!("{}", ans);
}
0