結果

問題 No.2421 entersys?
ユーザー haihamabossu
提出日時 2023-08-12 15:17:39
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 487 ms / 3,000 ms
コード長 8,010 bytes
コンパイル時間 15,846 ms
コンパイル使用メモリ 384,428 KB
実行使用メモリ 40,632 KB
最終ジャッジ日時 2024-11-20 01:07:24
合計ジャッジ時間 25,068 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

//https://github.com/rust-lang-ja/ac-library-rs
pub mod fenwicktree {
use std::ops::{Bound, RangeBounds};
// Reference: https://en.wikipedia.org/wiki/Fenwick_tree
pub struct FenwickTree<T> {
n: usize,
ary: Vec<T>,
e: T,
}
impl<T: Clone + std::ops::AddAssign<T>> FenwickTree<T> {
pub fn new(n: usize, e: T) -> Self {
FenwickTree {
n,
ary: vec![e.clone(); n],
e,
}
}
pub fn accum(&self, mut idx: usize) -> T {
let mut sum = self.e.clone();
while idx > 0 {
sum += self.ary[idx - 1].clone();
idx &= idx - 1;
}
sum
}
/// performs data[idx] += val;
pub fn add<U: Clone>(&mut self, mut idx: usize, val: U)
where
T: std::ops::AddAssign<U>,
{
let n = self.n;
idx += 1;
while idx <= n {
self.ary[idx - 1] += val.clone();
idx += idx & idx.wrapping_neg();
}
}
/// Returns data[l] + ... + data[r - 1].
pub fn sum<R>(&self, range: R) -> T
where
T: std::ops::Sub<Output = T>,
R: RangeBounds<usize>,
{
let r = match range.end_bound() {
Bound::Included(r) => r + 1,
Bound::Excluded(r) => *r,
Bound::Unbounded => self.n,
};
let l = match range.start_bound() {
Bound::Included(l) => *l,
Bound::Excluded(l) => l + 1,
Bound::Unbounded => return self.accum(r),
};
self.accum(r) - self.accum(l)
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::ops::Bound::*;
#[test]
fn fenwick_tree_works() {
let mut bit = FenwickTree::new(5, 0i64);
// [1, 2, 3, 4, 5]
for i in 0..5 {
bit.add(i, i as i64 + 1);
}
assert_eq!(bit.sum(0..5), 15);
assert_eq!(bit.sum(0..4), 10);
assert_eq!(bit.sum(1..3), 5);
assert_eq!(bit.sum(..), 15);
assert_eq!(bit.sum(..2), 3);
assert_eq!(bit.sum(..=2), 6);
assert_eq!(bit.sum(1..), 14);
assert_eq!(bit.sum(1..=3), 9);
assert_eq!(bit.sum((Excluded(0), Included(2))), 5);
}
}
}
use fenwicktree::*;
pub mod compression {
pub struct Compression<T: Copy + Ord> {
pub id: std::collections::BTreeMap<T, usize>,
pub rev: Vec<T>,
}
impl<T: Copy + Ord> Compression<T> {
pub fn new() -> Self {
Self {
id: std::collections::BTreeMap::new(),
rev: vec![],
}
}
pub fn add(&mut self, key: T) {
self.id.entry(key).or_insert(0);
}
pub fn compress(mut self) -> (std::collections::BTreeMap<T, usize>, Vec<T>) {
self.rev = vec![];
for (k, v) in self.id.iter_mut() {
*v = self.rev.len();
self.rev.push(*k);
}
(self.id, self.rev)
}
}
}
pub mod scanner {
pub struct Scanner {
buf: Vec<String>,
}
impl Scanner {
pub fn new() -> Self {
Self { buf: vec![] }
}
pub fn new_from(source: &str) -> Self {
let source = String::from(source);
let buf = Self::split(source);
Self { buf }
}
pub fn next<T: std::str::FromStr>(&mut self) -> T {
loop {
if let Some(x) = self.buf.pop() {
return x.parse().ok().expect("");
}
let mut source = String::new();
std::io::stdin().read_line(&mut source).expect("");
self.buf = Self::split(source);
}
}
fn split(source: String) -> Vec<String> {
source
.split_whitespace()
.rev()
.map(String::from)
.collect::<Vec<_>>()
}
}
}
use crate::FenwickTree;
use crate::{compression::Compression, scanner::Scanner};
use std::{collections::BTreeMap, io::Write};
fn main() {
let mut scanner = Scanner::new();
let out = std::io::stdout();
let mut out = std::io::BufWriter::new(out.lock());
let t: usize = 1;
for _ in 0..t {
solve(&mut scanner, &mut out);
}
}
fn name_id(s: String) -> usize {
let mut res = 0;
let mut b = 1;
for c in s.chars().rev() {
let now = c as usize - 'a' as usize + 1;
res += now * b;
b *= 27;
}
res
}
fn solve(scanner: &mut Scanner, out: &mut std::io::BufWriter<std::io::StdoutLock>) {
let n: usize = scanner.next();
let xlr = (0..n)
.map(|_| {
(
name_id(scanner.next::<String>()),
scanner.next::<usize>(),
scanner.next::<usize>(),
)
})
.collect::<Vec<_>>();
let q: usize = scanner.next();
let qs = (0..q)
.map(|_| {
let qt = scanner.next::<usize>();
let (x, t, l, r) = if qt == 1 {
(
name_id(scanner.next::<String>()),
scanner.next::<usize>(),
0,
0,
)
} else if qt == 2 {
(0, scanner.next::<usize>(), 0, 0)
} else {
(
name_id(scanner.next::<String>()),
0,
scanner.next::<usize>(),
scanner.next::<usize>(),
)
};
(qt, x, t, l, r)
})
.collect::<Vec<_>>();
let mut map = BTreeMap::new();
for i in 0..n {
let (x, l, r) = xlr[i];
map.entry(x).or_insert(vec![]).push((0, 0, 0, l, r));
}
for i in 0..q {
let (qt, x, t, l, r) = qs[i];
if qt == 1 || qt == 3 {
map.entry(x).or_insert(vec![]).push((qt, i, t, l, r));
}
}
let mut ans = vec![0; q];
for (_, list) in map.iter() {
let mut compression = Compression::new();
compression.add(0);
compression.add(1e9 as usize + 5);
for &(_, _, t, l, r) in list.iter() {
compression.add(t);
compression.add(l);
compression.add(r);
}
let (id, _) = compression.compress();
let mut bit = FenwickTree::new(id.len(), 0isize);
for &(qt, qi, t, l, r) in list.iter() {
if qt == 0 || qt == 3 {
bit.add(id[&l], 1);
bit.add(id[&r] + 1, -1);
} else {
ans[qi] = bit.sum(0..=id[&t]);
}
}
}
let mut compression = Compression::new();
compression.add(0);
compression.add(1e9 as usize + 5);
for &(_, l, r) in xlr.iter() {
compression.add(l);
compression.add(r);
}
for &(_, _, t, l, r) in qs.iter() {
compression.add(t);
compression.add(l);
compression.add(r);
}
let (id, _) = compression.compress();
let mut bit = FenwickTree::new(id.len(), 0isize);
for &(_, l, r) in xlr.iter() {
bit.add(id[&l], 1);
bit.add(id[&r] + 1, -1);
}
for qi in 0..q {
let (qt, _, t, l, r) = qs[qi];
if qt == 2 {
ans[qi] = bit.sum(0..=id[&t]);
}
if qt == 3 {
bit.add(id[&l], 1);
bit.add(id[&r] + 1, -1);
}
}
for qi in 0..q {
let qt = qs[qi].0;
if qt == 1 {
if ans[qi] > 0 {
writeln!(out, "Yes").unwrap();
} else {
writeln!(out, "No").unwrap();
}
}
if qt == 2 {
writeln!(out, "{}", ans[qi]).unwrap();
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0