Submission #1864725
Source Code Expand
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet, BinaryHeap, VecDeque, BTreeSet, BTreeMap};
#[allow(unused_imports)]
use std::iter::FromIterator;
#[allow(unused_imports)]
use std::io::stdin;
mod util {
use std::io::stdin;
use std::str::FromStr;
use std::fmt::Debug;
#[allow(dead_code)]
pub fn line() -> String {
let mut line: String = String::new();
stdin().read_line(&mut line).unwrap();
line.trim().to_string()
}
#[allow(dead_code)]
pub fn gets<T: FromStr>() -> Vec<T>
where
<T as FromStr>::Err: Debug,
{
let mut line: String = String::new();
stdin().read_line(&mut line).unwrap();
line.split_whitespace()
.map(|t| t.parse().unwrap())
.collect()
}
}
#[allow(unused_macros)]
macro_rules! get {
($t:ty) => {
{
let mut line: String = String::new();
stdin().read_line(&mut line).unwrap();
line.trim().parse::<$t>().unwrap()
}
};
($($t:ty),*) => {
{
let mut line: String = String::new();
stdin().read_line(&mut line).unwrap();
let mut iter = line.split_whitespace();
(
$(iter.next().unwrap().parse::<$t>().unwrap(),)*
)
}
};
($t:ty; $n:expr) => {
(0..$n).map(|_|
get!($t)
).collect::<Vec<_>>()
};
($($t:ty),*; $n:expr) => {
(0..$n).map(|_|
get!($($t),*)
).collect::<Vec<_>>()
};
($t:ty ;;) => {
{
let mut line: String = String::new();
stdin().read_line(&mut line).unwrap();
line.split_whitespace()
.map(|t| t.parse::<$t>().unwrap())
.collect::<Vec<_>>()
}
};
}
#[allow(unused_macros)]
macro_rules! debug {
($($a:expr),*) => {
println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
}
}
struct SEG<T: Clone, F: Fn(&T, &T) -> T> {
n: usize,
buf: Vec<T>,
reducer: F,
}
impl<T: Clone, F: Fn(&T, &T) -> T> SEG<T, F> {
fn new(n: usize, zero: &T, f: F) -> SEG<T, F> {
let n = (1..)
.map(|i| 2usize.pow(i as u32))
.find(|&x| x > n)
.unwrap();
SEG {
n: n,
buf: vec![zero.clone(); 2 * n],
reducer: f,
}
}
fn update(&mut self, k: usize, a: T) {
let mut k = k + self.n - 1;
self.buf[k] = a;
while k > 0 {
k = (k - 1) / 2;
self.buf[k] = (self.reducer)(&self.buf[k * 2 + 1], &self.buf[k * 2 + 2]);
}
}
fn add(&mut self, k: usize, a: &T) {
let mut k = k + self.n - 1;
self.buf[k] = (self.reducer)(&self.buf[k], a);
while k > 0 {
k = (k - 1) / 2;
self.buf[k] = (self.reducer)(&self.buf[k * 2 + 1], &self.buf[k * 2 + 2]);
}
}
fn q(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> Option<T> {
if r <= a || b <= l {
return None;
}
if a <= l && r <= b {
Some(self.buf[k].clone())
} else {
let vl = self.q(a, b, k * 2 + 1, l, (l + r) / 2);
let vr = self.q(a, b, k * 2 + 2, (l + r) / 2, r);
match (vl, vr) {
(Some(l), Some(r)) => Some((self.reducer)(&l, &r)),
(Some(l), None) => Some(l),
(None, Some(r)) => Some(r),
_ => None,
}
}
}
fn query(&self, a: usize, b: usize) -> T {
self.q(a, b, 0, 0, self.n).unwrap()
}
}
fn shorten(ab: (usize, usize)) -> (usize, usize) {
if ab.0 > ab.1 {
let t = ab.0 - ab.1;
match t % 3 {
2 => (0, 1),
x => (x, 0),
}
} else {
let t = ab.1 - ab.0;
match t % 3 {
2 => (1, 0),
x => (0, x),
}
}
}
fn main() {
let s = util::line();
let t = util::line();
let mut segs = SEG::new(s.len(), &(0, 0), |t1, t2| (t1.0 + t2.0, t1.1 + t2.1));
let mut segt = SEG::new(t.len(), &(0, 0), |t1, t2| (t1.0 + t2.0, t1.1 + t2.1));
let q = get!(usize);
for (i, c) in s.chars().enumerate() {
segs.update(i, if c == 'A' { (1, 0) } else { (0, 1) });
}
for (i, c) in t.chars().enumerate() {
segt.update(i, if c == 'A' { (1, 0) } else { (0, 1) });
}
for _ in 0..q {
let (a, b, c, d) = get!(usize, usize, usize, usize);
if shorten(segs.query(a - 1, b)) == shorten(segt.query(c - 1, d)) {
println!("YES");
} else {
println!("NO");
}
}
}
Submission Info
Submission Time |
|
Task |
E - TrBBnsformBBtion |
User |
hatoo |
Language |
Rust (1.15.1) |
Score |
600 |
Code Size |
4992 Byte |
Status |
AC |
Exec Time |
321 ms |
Memory |
12796 KB |
Compile Error
warning: method is never used: `add`, #[warn(dead_code)] on by default
--> ./Main.rs:111:5
|
111 | fn add(&mut self, k: usize, a: &T) {
| ^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
600 / 600 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_000.txt, 0_001.txt |
All |
0_000.txt, 0_001.txt, bound_0.txt, bound_1.txt, bound_2.txt, bound_3.txt, min.txt, rnd_10000_10.txt, rnd_10000_10000.txt, rnd_10000_2.txt, rnd_10_10.txt, rnd_10_10000.txt, rnd_10_2.txt, rnd_2_10.txt, rnd_2_10000.txt, rnd_2_2.txt |
Case Name |
Status |
Exec Time |
Memory |
0_000.txt |
AC |
2 ms |
4352 KB |
0_001.txt |
AC |
2 ms |
4352 KB |
bound_0.txt |
AC |
254 ms |
12796 KB |
bound_1.txt |
AC |
281 ms |
12796 KB |
bound_2.txt |
AC |
276 ms |
12796 KB |
bound_3.txt |
AC |
295 ms |
12796 KB |
min.txt |
AC |
2 ms |
4352 KB |
rnd_10000_10.txt |
AC |
308 ms |
12796 KB |
rnd_10000_10000.txt |
AC |
321 ms |
12796 KB |
rnd_10000_2.txt |
AC |
320 ms |
12796 KB |
rnd_10_10.txt |
AC |
321 ms |
12796 KB |
rnd_10_10000.txt |
AC |
317 ms |
12796 KB |
rnd_10_2.txt |
AC |
316 ms |
12796 KB |
rnd_2_10.txt |
AC |
313 ms |
12796 KB |
rnd_2_10000.txt |
AC |
313 ms |
12796 KB |
rnd_2_2.txt |
AC |
313 ms |
12796 KB |