結果
問題 | No.2421 entersys? |
ユーザー |
|
提出日時 | 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 |
ソースコード
//https://github.com/rust-lang-ja/ac-library-rspub mod fenwicktree {use std::ops::{Bound, RangeBounds};// Reference: https://en.wikipedia.org/wiki/Fenwick_treepub 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)whereT: 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) -> TwhereT: 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();}}}