049.rs

#![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);
}

gen.py

n = 100000
m = n

print(n, m)

for i in range(m):
    print(i + 1, 1, i + 1)