#546155 (Rust) No.1209 XOR Into You

• 問題: No.1209 XOR Into You
• ユーザー: ikd
• 提出日時: 2020-09-02 22:40:41
• 言語: Rust (1.77.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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	1 ms; 5,248 KB
testcase_04	AC	72 ms; 6,864 KB
testcase_05	WA	-
testcase_06	AC	71 ms; 6,864 KB
testcase_07	AC	123 ms; 12,984 KB
testcase_08	AC	108 ms; 11,900 KB
testcase_09	AC	105 ms; 12,028 KB
testcase_10	AC	88 ms; 9,968 KB
testcase_11	AC	108 ms; 11,736 KB
testcase_12	AC	99 ms; 11,008 KB
testcase_13	AC	118 ms; 12,300 KB
testcase_14	AC	95 ms; 10,816 KB
testcase_15	AC	104 ms; 11,356 KB
testcase_16	AC	98 ms; 11,040 KB
testcase_17	AC	91 ms; 10,752 KB
testcase_18	AC	141 ms; 14,524 KB
testcase_19	AC	101 ms; 11,168 KB
testcase_20	AC	118 ms; 12,444 KB
testcase_21	AC	84 ms; 9,856 KB
testcase_22	AC	87 ms; 15,232 KB
testcase_23	AC	87 ms; 15,360 KB
testcase_24	AC	87 ms; 15,088 KB
testcase_25	AC	135 ms; 15,208 KB
testcase_26	AC	135 ms; 15,120 KB
testcase_27	AC	137 ms; 15,188 KB
testcase_28	AC	132 ms; 15,056 KB
testcase_29	AC	132 ms; 15,156 KB
testcase_30	AC	139 ms; 15,184 KB
testcase_31	AC	97 ms; 8,528 KB
testcase_32	AC	97 ms; 8,528 KB
testcase_33	AC	97 ms; 8,528 KB
testcase_34	AC	99 ms; 8,528 KB
testcase_35	AC	97 ms; 8,656 KB
testcase_36	AC	97 ms; 8,656 KB
testcase_37	AC	68 ms; 8,704 KB
testcase_38	AC	114 ms; 12,840 KB
testcase_39	AC	95 ms; 11,592 KB
testcase_40	AC	85 ms; 15,308 KB

ソースコード

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