Submission #3415933
Source Code Expand
/// Thank you tanakh!!!
/// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let mut s = {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
s
};
let mut iter = s.split_whitespace();
input_inner!{iter, $($r)*}
};
}
macro_rules! input_inner {
($iter:expr) => {};
($iter:expr, ) => {};
($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($iter, $t);
input_inner!{$iter $($r)*}
};
}
macro_rules! read_value {
($iter:expr, ( $($t:tt),* )) => {
( $(read_value!($iter, $t)),* )
};
($iter:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
};
($iter:expr, chars) => {
read_value!($iter, String).chars().collect::<Vec<char>>()
};
($iter:expr, usize1) => {
read_value!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
use std::collections::BTreeSet;
struct Data {
positive: BTreeSet<(i64, i64, usize)>,
negative: BTreeSet<(i64, i64, usize)>,
}
impl Data {
fn new(lr: &Vec<(i64, i64)>) -> Self {
let mut positive_set = BTreeSet::new();
let mut negative_set = BTreeSet::new();
let n = lr.len();
for i in 0..n {
let (l, r) = lr[i];
positive_set.insert((l, r, i));
negative_set.insert((r, l, i));
}
Data {
positive: positive_set,
negative: negative_set,
}
}
fn pop_min(&mut self) -> (i64, i64) {
assert_eq!(self.positive.len(), self.negative.len());
assert!(!self.negative.is_empty());
let &(r, l, i) = self.negative.iter().next().unwrap();
self.negative.remove(&(r, l, i));
self.positive.remove(&(l, r, i));
(l, r)
}
fn pop_max(&mut self) -> (i64, i64) {
assert_eq!(self.positive.len(), self.negative.len());
assert!(!self.positive.is_empty());
let &(l, r, i) = self.positive.iter().next_back().unwrap();
self.negative.remove(&(r, l, i));
self.positive.remove(&(l, r, i));
(l, r)
}
fn len(&self) -> usize {
assert_eq!(self.positive.len(), self.negative.len());
self.negative.len()
}
}
fn solve(mut data: Data) -> i64 {
let mut cur = 0;
let mut ans = 0;
let n = data.len();
for i in 0..n {
let (l, r) = if i % 2 == 0 {
data.pop_max()
} else {
data.pop_min()
};
assert!(l < r);
let (move_dist, next) = if cur < l {
(l - cur, l)
} else if r < cur {
(cur - r, r)
} else {
(0, cur)
};
ans += move_dist;
cur = next;
}
ans + (cur - 0).abs()
}
use std::cmp;
fn main() {
input!(n: usize, lr: [(i64, i64); n]);
let data = Data::new(&lr);
let ans1 = solve(data);
let neg_lr = lr.iter().map(|&(l, r)| (-r, -l)).collect::<Vec<_>>();
let data = Data::new(&neg_lr);
let ans2 = solve(data);
println!("{}", cmp::max(ans1, ans2));
}
Submission Info
Submission Time
2018-10-16 10:08:11+0900
Task
C - Interval Game
User
kenkoooo
Language
Rust (1.15.1)
Score
700
Code Size
3550 Byte
Status
AC
Exec Time
145 ms
Memory
18560 KB
Compile Error
warning: variable does not need to be mutable, #[warn(unused_mut)] on by default
--> ./Main.rs:9:13
|
9 | let mut s = {
| ^^^^^
...
125 | input!(n: usize, lr: [(i64, i64); n]);
| -------------------------------------- in this macro invocation
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
700 / 700
Status
Set Name
Test Cases
Sample
sample01.txt, sample02.txt, sample03.txt
All
sample01.txt, sample02.txt, sample03.txt, in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in40.txt, sample01.txt, sample02.txt, sample03.txt
Case Name
Status
Exec Time
Memory
in01.txt
AC
81 ms
12368 KB
in02.txt
AC
136 ms
16384 KB
in03.txt
AC
75 ms
12496 KB
in04.txt
AC
41 ms
8444 KB
in05.txt
AC
81 ms
12396 KB
in06.txt
AC
138 ms
16636 KB
in07.txt
AC
86 ms
12452 KB
in08.txt
AC
23 ms
6396 KB
in09.txt
AC
76 ms
12388 KB
in10.txt
AC
72 ms
12512 KB
in11.txt
AC
142 ms
18336 KB
in12.txt
AC
145 ms
18388 KB
in13.txt
AC
141 ms
18348 KB
in14.txt
AC
141 ms
18404 KB
in15.txt
AC
141 ms
18308 KB
in16.txt
AC
141 ms
18388 KB
in17.txt
AC
141 ms
18380 KB
in18.txt
AC
141 ms
18324 KB
in19.txt
AC
141 ms
18388 KB
in20.txt
AC
141 ms
18388 KB
in21.txt
AC
138 ms
18560 KB
in22.txt
AC
138 ms
18460 KB
in23.txt
AC
139 ms
18508 KB
in24.txt
AC
140 ms
18548 KB
in25.txt
AC
138 ms
18460 KB
in26.txt
AC
138 ms
18388 KB
in27.txt
AC
137 ms
18320 KB
in28.txt
AC
139 ms
18296 KB
in29.txt
AC
138 ms
18296 KB
in30.txt
AC
138 ms
18436 KB
in31.txt
AC
140 ms
18428 KB
in32.txt
AC
141 ms
18380 KB
in33.txt
AC
141 ms
18376 KB
in34.txt
AC
140 ms
18404 KB
in35.txt
AC
141 ms
18312 KB
in36.txt
AC
140 ms
18404 KB
in37.txt
AC
141 ms
18320 KB
in38.txt
AC
140 ms
18316 KB
in39.txt
AC
141 ms
18352 KB
in40.txt
AC
140 ms
18328 KB
sample01.txt
AC
2 ms
4352 KB
sample02.txt
AC
2 ms
4352 KB
sample03.txt
AC
2 ms
4352 KB