結果
問題 | No.1209 XOR Into You |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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] < ximpl<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] < xwhile 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] <= xfn upper_bound(&self, x: &T) -> usize {if self[0] > *x {return 0;}let mut lf = 0;let mut rg = self.len();// self[lf] <= xwhile 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);}