結果

問題 No.1209 XOR Into You
ユーザー ikdikd
提出日時 2020-09-02 22:41:50
言語 Rust
(1.77.0)
結果
AC  
実行時間 141 ms / 2,000 ms
コード長 4,472 bytes
コンパイル時間 1,939 ms
コンパイル使用メモリ 163,300 KB
実行使用メモリ 15,156 KB
最終ジャッジ日時 2023-08-14 05:20:10
合計ジャッジ時間 8,854 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,384 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 49 ms
4,384 KB
testcase_05 AC 50 ms
4,384 KB
testcase_06 AC 66 ms
6,964 KB
testcase_07 AC 111 ms
12,916 KB
testcase_08 AC 102 ms
11,792 KB
testcase_09 AC 103 ms
11,752 KB
testcase_10 AC 78 ms
9,932 KB
testcase_11 AC 99 ms
11,688 KB
testcase_12 AC 95 ms
11,056 KB
testcase_13 AC 109 ms
12,456 KB
testcase_14 AC 96 ms
10,684 KB
testcase_15 AC 102 ms
11,404 KB
testcase_16 AC 100 ms
11,068 KB
testcase_17 AC 96 ms
10,680 KB
testcase_18 AC 141 ms
14,448 KB
testcase_19 AC 102 ms
11,080 KB
testcase_20 AC 117 ms
12,520 KB
testcase_21 AC 88 ms
9,816 KB
testcase_22 AC 83 ms
15,124 KB
testcase_23 AC 83 ms
15,084 KB
testcase_24 AC 82 ms
15,096 KB
testcase_25 AC 135 ms
15,124 KB
testcase_26 AC 134 ms
15,144 KB
testcase_27 AC 136 ms
15,124 KB
testcase_28 AC 139 ms
15,096 KB
testcase_29 AC 131 ms
15,144 KB
testcase_30 AC 129 ms
15,068 KB
testcase_31 AC 90 ms
8,572 KB
testcase_32 AC 90 ms
8,476 KB
testcase_33 AC 91 ms
8,592 KB
testcase_34 AC 94 ms
8,588 KB
testcase_35 AC 90 ms
8,560 KB
testcase_36 AC 93 ms
8,564 KB
testcase_37 AC 62 ms
8,596 KB
testcase_38 AC 102 ms
12,800 KB
testcase_39 AC 91 ms
11,772 KB
testcase_40 AC 82 ms
15,156 KB
権限があれば一括ダウンロードができます

ソースコード

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();

    if a[0] != b[0] || a[n - 1] != b[n - 1] {
        println!("-1");
        return;
    }

    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