Skip to content

Instantly share code, notes, and snippets.

@tamuhey
Last active June 27, 2021 03:12
Show Gist options
  • Save tamuhey/cab2292183c2c46430b79aea3eb1a82b to your computer and use it in GitHub Desktop.
Save tamuhey/cab2292183c2c46430b79aea3eb1a82b to your computer and use it in GitHub Desktop.
#![allow(unused_imports)]
#![allow(unused_macros)]
use std::cmp::Reverse as R;
use std::collections::*;
use std::io::{stdin, BufWriter, Read, Write};
use std::mem;
#[allow(unused_macros)]
macro_rules! parse {
($it: ident ) => {};
($it: ident, ) => {};
($it: ident, $var:ident : $t:tt $($r:tt)*) => {
let $var = parse_val!($it, $t);
parse!($it $($r)*);
};
($it: ident, mut $var:ident : $t:tt $($r:tt)*) => {
let mut $var = parse_val!($it, $t);
parse!($it $($r)*);
};
($it: ident, $var:ident $($r:tt)*) => {
let $var = parse_val!($it, usize);
parse!($it $($r)*);
};
}
#[allow(unused_macros)]
macro_rules! parse_val {
($it: ident, [$t:tt; $len:expr]) => {
(0..$len).map(|_| parse_val!($it, $t)).collect::<Vec<_>>();
};
($it: ident, ($($t: tt),*)) => {
($(parse_val!($it, $t)),*)
};
($it: ident, u1) => {
$it.next().unwrap().parse::<usize>().unwrap() -1
};
($it: ident, $t: ty) => {
$it.next().unwrap().parse::<$t>().unwrap()
};
}
fn solve(s: &str) {
let mut it = s.split_whitespace();
parse!(it, n: usize, m: usize);
if n > m {
println!("{}", -1);
return;
}
let mut ranges = vec![BinaryHeap::<(R<i64>, usize)>::new(); n + 1];
for _ in 0..m {
parse!(it, ci: i64, li: u1, ri: usize);
ranges[li].push((R(ci), ri));
}
let mut ret = 0i64;
// 掃き出し法 (最悪O(N^2))
for i in 0..n {
// 最もciが小さいものを使って掃き出す
if let Some((R(c), r)) = ranges[i].pop() {
ret += c;
for (ci, ri) in mem::take(&mut ranges[i]).drain() {
// 全ての要素が0になったので取り除く
if ri == r {
continue;
}
// 掃き出しで要素に変更があったものを更新する
let (li, ri) = if r < ri { (r, ri) } else { (ri, r) };
ranges[li].push((ci, ri));
}
} else {
println!("{}", -1);
return;
}
}
println!("{}", ret);
}
fn main() {
let mut s = String::new();
stdin().read_to_string(&mut s).unwrap();
solve(&s);
}
n = 100000
m = n
print(n, m)
for i in range(m):
print(i + 1, 1, i + 1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment