結果
問題 | No.743 Segments on a Polygon |
ユーザー |
![]() |
提出日時 | 2018-10-05 22:25:24 |
言語 | Rust (1.83.0 + proconio) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 11,487 bytes |
コンパイル時間 | 11,901 ms |
コンパイル使用メモリ | 387,296 KB |
最終ジャッジ日時 | 2024-11-14 20:38:56 |
合計ジャッジ時間 | 13,271 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
error[E0432]: unresolved import `io` --> src/main.rs:354:9 | 354 | use io::FromBytes; | ^^ help: a similar path exists: `crate::io` | = note: `use` statements changed in Rust 2018; read more at <https://doc.rust-lang.org/edition-guide/rust-2018/module-system/path-clarity.html> error[E0432]: unresolved import `misc` --> src/main.rs:275:9 | 275 | use misc::ByteChar; | ^^^^ help: a similar path exists: `crate::misc` | = note: `use` statements changed in Rust 2018; read more at <https://doc.rust-lang.org/edition-guide/rust-2018/module-system/path-clarity.html> error[E0432]: unresolved import `misc` --> src/main.rs:307:9 | 307 | use misc::{ByteChar, ByteString}; | ^^^^ help: a similar path exists: `crate::misc` | = note: `use` statements changed in Rust 2018; read more at <https://doc.rust-lang.org/edition-guide/rust-2018/module-system/path-clarity.html> For more information about this error, try `rustc --explain E0432`. error: could not compile `main` (bin "main") due to 3 previous errors
ソースコード
fn solve<R: BufRead, W: Write>(_reader: R, _writer: &mut W) {let mut _scanner = Scanner::new(_reader);#[allow(unused_macros)]macro_rules! scan {($T:ty) => {_scanner.next::<$T>().unwrap()};($($T:ty),+) => {($(scan!($T)),+)};($($T:ty),+; $n:expr $(; $m:expr)*) => {{let mut vec = Vec::with_capacity($n);for _ in 0..$n {vec.push(scan!($($T),+ $(; $m)*));}vec}};}#[allow(unused_macros)]macro_rules! scan_iter {($T:ty; $n:expr) => {_scanner.take::<$T>($n).map(|x| x.unwrap())};}#[allow(unused_macros)]macro_rules! print {($fmt:expr) => {write!(_writer, $fmt).unwrap()};($fmt:expr, $($arg:tt)*) => {write!(_writer, $fmt, $($arg)*).unwrap()};}#[allow(unused_macros)]macro_rules! println {($fmt:expr) => {writeln!(_writer, $fmt).unwrap()};($fmt:expr, $($arg:tt)*) => {writeln!(_writer, $fmt, $($arg)*).unwrap()};}#[allow(unused_macros)]macro_rules! eprint {($fmt:expr) => {#[cfg(debug_assertions)]write!(::std::io::stderr(), $fmt).unwrap()};($fmt:expr, $($arg:tt)*) => {#[cfg(debug_assertions)]write!(::std::io::stderr(), $fmt, $($arg)*).unwrap()};}#[allow(unused_macros)]macro_rules! eprintln {($fmt:expr) => {#[cfg(debug_assertions)]writeln!(::std::io::stderr(), $fmt).unwrap()};($fmt:expr, $($arg:tt)*) => {#[cfg(debug_assertions)]writeln!(::std::io::stderr(), $fmt, $($arg)*).unwrap()};}#[allow(unused_macros)]macro_rules! dump {($($x:expr),+) => {eprint!("[{}:{}] ", file!(), line!());eprintln!(concat!($(stringify!($x), " = {:?}; "),+), $($x),+);};}use foreign_lib::LazySegTree;let (n, m) = scan!(usize, usize);let mut ab = vec![];for _ in 0..n {let (a, b) = scan!(usize, usize);ab.push(if a < b { (a, b) } else { (b, a) });}ab.sort();let mut seq = LazySegTree::new(m, |l, r| l + r, 0isize, |x, o| x + o, |l, r| l + r, 0isize);let mut ans = 0;for (a, b) in ab {ans += (seq.query(a, a) - seq.query(b, b)).abs();seq.update(a, b, 1);}println!("{}", ans);}const CUSTOM_STACK_SIZE_MEBIBYTES: Option<usize> = None;fn main() {if let Some(stack_size_mebibytes) = CUSTOM_STACK_SIZE_MEBIBYTES {let builder = thread::Builder::new().name("exec_solver".to_string()).stack_size(stack_size_mebibytes * 1024 * 1024);builder.spawn(exec_solver).unwrap().join().unwrap();} else {exec_solver();}}fn exec_solver() {let stdin = stdin();let stdout = stdout();#[cfg(debug_assertions)]let mut writer = stdout.lock();#[cfg(not(debug_assertions))]let mut writer = ::std::io::BufWriter::new(stdout.lock());solve(stdin.lock(), &mut writer);writer.flush().unwrap();}use io::Scanner;use std::io::{stdin, stdout, BufRead, Write};use std::thread;mod foreign_lib {#![allow(unused)]// https://github.com/koba-e964/contest/blob/98387e5fc72350e0a96034b17df9fc2beef95123/comm/LazySegTree-poly.rs/*** Lazy Segment Tree. This data structure is useful for fast folding and updating on intervals of an array* whose elements are elements of monoid T. Note that constructing this tree requires the identity* element of T and the operation of T. upop must distribute over biop.* Reference: http://d.hatena.ne.jp/kyuridenamida/20121114/1352835261* Verified by s8pc-2 H (http://s8pc-2.contest.atcoder.jp/submissions/1587536)*/pub struct LazySegTree<T, U, BiOp, UpOp, UpComp> {n: usize,dat: Vec<T>,lazy: Vec<U>,e: T,biop: BiOp,upop: UpOp,upcomp: UpComp,upe: U, // identity for upop}impl<T: Clone + Copy, U: Clone + Copy, BiOp: Fn(T, T) -> T, UpOp: Fn(T, U) -> T, UpComp: Fn(U, U) -> U>LazySegTree<T, U, BiOp, UpOp, UpComp>{pub fn new(n_: usize, biop: BiOp, e: T, upop: UpOp, upcomp: UpComp, upe: U) -> Self {let mut n = 1;while n < n_ {n *= 2;} // n is a power of 2LazySegTree {n: n,dat: vec![e; 2 * n - 1],lazy: vec![upe; 2 * n - 1],e: e,biop: biop,upop: upop,upcomp: upcomp,upe: upe,}}#[inline]fn lazy_evaluate_node(&mut self, k: usize) {self.dat[k] = (self.upop)(self.dat[k], self.lazy[k]); // TODO How do biop and upop interact? biop = max, upop = (+) are assumedif k < self.n - 1 {self.lazy[2 * k + 1] = (self.upcomp)(self.lazy[2 * k + 1], self.lazy[k]);self.lazy[2 * k + 2] = (self.upcomp)(self.lazy[2 * k + 2], self.lazy[k]);}self.lazy[k] = self.upe; // identity for upop}#[inline]fn update_node(&mut self, k: usize) {self.dat[k] = (self.biop)(self.dat[2 * k + 1], self.dat[2 * k + 2]);}fn update_sub(&mut self, a: usize, b: usize, v: U, k: usize, l: usize, r: usize) {self.lazy_evaluate_node(k);// [a,b) and [l,r) intersects?if r <= a || b <= l {return;}if a <= l && r <= b {self.lazy[k] = (self.upcomp)(self.lazy[k], v);self.lazy_evaluate_node(k);return;}self.update_sub(a, b, v, 2 * k + 1, l, (l + r) / 2);self.update_sub(a, b, v, 2 * k + 2, (l + r) / 2, r);self.update_node(k);}/* ary[i] = upop(ary[i], v) for i in [a, b] (inclusive) */#[inline]pub fn update(&mut self, a: usize, b: usize, v: U) {let n = self.n;self.update_sub(a, b + 1, v, 0, 0, n);}fn update_single_sub(&mut self, a: usize, v: T, k: usize, l: usize, r: usize) {self.lazy_evaluate_node(k);// [a,b) and [l,r) intersects?if r <= a || a < l {return;}if a == l && r == a + 1 {self.dat[k] = v;return;}self.update_single_sub(a, v, 2 * k + 1, l, (l + r) / 2);self.update_single_sub(a, v, 2 * k + 2, (l + r) / 2, r);self.update_node(k);}/* ary[i] = upop(ary[i], v) for i in [a, b] (inclusive) */#[inline]pub fn update_single(&mut self, a: usize, v: T) {let n = self.n;self.update_single_sub(a, v, 0, 0, n);}/* l,r are for simplicity */fn query_sub(&mut self, a: usize, b: usize, k: usize, l: usize, r: usize) -> T {self.lazy_evaluate_node(k);// [a,b) and [l,r) intersect?if r <= a || b <= l {return self.e;}if a <= l && r <= b {return self.dat[k];}let vl = self.query_sub(a, b, 2 * k + 1, l, (l + r) / 2);let vr = self.query_sub(a, b, 2 * k + 2, (l + r) / 2, r);self.update_node(k);return (self.biop)(vl, vr);}/* [a, b] (note: inclusive) */#[inline]pub fn query(&mut self, a: usize, b: usize) -> T {let n = self.n;self.query_sub(a, b + 1, 0, 0, n)}}}pub mod misc {pub use self::byte_char::*;pub use self::byte_string::*;mod byte_char {use std::fmt::{self, Debug, Display, Formatter};#[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash)]pub struct ByteChar(pub u8);impl Debug for ByteChar {fn fmt(&self, f: &mut Formatter) -> fmt::Result {write!(f, "b\'{}\'", self.0 as char)}}impl Display for ByteChar {fn fmt(&self, f: &mut Formatter) -> fmt::Result {write!(f, "{}", self.0 as char)}}}mod byte_string {use misc::ByteChar;use std::fmt::{self, Debug, Display, Formatter};#[derive(Clone, PartialOrd, Ord, PartialEq, Eq, Hash)]pub struct ByteString(pub Vec<ByteChar>);impl Debug for ByteString {fn fmt(&self, f: &mut Formatter) -> fmt::Result {write!(f, "b\"")?;for &c in &self.0 {write!(f, "{}", c.0 as char)?;}write!(f, "b\"")}}impl Display for ByteString {fn fmt(&self, f: &mut Formatter) -> fmt::Result {for &c in &self.0 {write!(f, "{}", c)?;}Ok(())}}}}pub mod io {pub use self::from_bytes::FromBytes;pub use self::scanner::Scanner;mod from_bytes {use misc::{ByteChar, ByteString};use std::str::{self, FromStr};#[derive(Debug)]pub struct FromBytesError;pub trait FromBytes: Sized {type Err;fn from_bytes(bytes: &[u8]) -> Result<Self, Self::Err>;}impl FromBytes for ByteChar {type Err = FromBytesError;fn from_bytes(bytes: &[u8]) -> Result<Self, Self::Err> {if bytes.len() == 1 {Ok(ByteChar(*unsafe { bytes.get_unchecked(0) }))} else {Err(FromBytesError)}}}impl FromBytes for ByteString {type Err = FromBytesError;fn from_bytes(bytes: &[u8]) -> Result<Self, Self::Err> {Ok(ByteString(bytes.iter().cloned().map(ByteChar).collect()))}}impl<T: FromStr> FromBytes for T {type Err = T::Err;fn from_bytes(bytes: &[u8]) -> Result<Self, Self::Err> {let s = if cfg!(debug_assertions) {str::from_utf8(bytes).unwrap()} else {unsafe { str::from_utf8_unchecked(bytes) }};T::from_str(s)}}}mod scanner {use io::FromBytes;use std::io::BufRead;use std::marker::PhantomData;pub struct Scanner<R> {reader: R,buffer: Vec<u8>,position: usize,}impl<R: BufRead> Scanner<R> {pub fn new(reader: R) -> Self {Scanner {reader: reader,buffer: vec![],position: 0,}}pub fn next<T: FromBytes>(&mut self) -> Result<T, T::Err> {FromBytes::from_bytes(self.next_bytes().unwrap_or(&[]))}pub fn take<T: FromBytes>(&mut self, n: usize) -> Take<R, T> {Take {scanner: self,n: n,_marker: PhantomData,}}pub fn next_bytes(&mut self) -> Option<&[u8]> {if self.buffer.is_empty() {self.read_line();}loop {match self.buffer.get(self.position) {Some(&b' ') => self.position += 1,Some(&b'\n') => self.read_line(),Some(_) => break,None => return None,}}let start = self.position;loop {match self.buffer.get(self.position) {Some(&b' ') | Some(&b'\n') | None => break,Some(_) => self.position += 1,}}Some(&self.buffer[start..self.position])}fn read_line(&mut self) {self.position = 0;self.buffer.clear();self.reader.read_until(b'\n', &mut self.buffer).unwrap();}}pub struct Take<'a, R: 'a, T> {scanner: &'a mut Scanner<R>,n: usize,_marker: PhantomData<fn() -> T>,}impl<'a, R: BufRead, T: FromBytes> Iterator for Take<'a, R, T> {type Item = Result<T, T::Err>;fn next(&mut self) -> Option<Self::Item> {if self.n > 0 {self.n -= 1;Some(self.scanner.next())} else {None}}fn size_hint(&self) -> (usize, Option<usize>) {(self.n, Some(self.n))}}impl<'a, R: BufRead, T: FromBytes> ExactSizeIterator for Take<'a, R, T> {}}}