結果
| 問題 | No.3665 Two Important Tasks |
| コンテスト | |
| ユーザー |
 akakimidori
|
| 提出日時 | 2026-08-30 15:05:10 |
| 言語 | Rust (1.97.1 + proconio + num + itertools) |
| 結果 |
AC
|
| 実行時間 | 704 ms / 4,000 ms |
| + 641µs | |
| コード長 | 14,135 bytes |
| 記録 | |
| コンパイル時間 | 11,394 ms |
| コンパイル使用メモリ | 206,248 KB |
| 実行使用メモリ | 184,704 KB |
| 最終ジャッジ日時 | 2026-08-30 15:05:32 |
| 合計ジャッジ時間 | 14,407 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 23 |
コンパイルメッセージ
warning: type alias `Set` is never used --> src/main.rs:5:6 | 5 | type Set<T> = BTreeSet<T>; | ^^^ | = note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default warning: type alias `Deque` is never used --> src/main.rs:6:6 | 6 | type Deque<T> = VecDeque<T>; | ^^^^^
ソースコード
use std::collections::*;
use std::io::Write;
type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;
fn main() {
input! {
n: usize,
q: usize,
item: [(usize1, usize, i64); n],
ask: [(usize1, usize1); q],
}
let mut query = vec![vec![]; n + 1];
for (i, &(l, r, _c)) in item.iter().enumerate() {
query[l].push((0, i));
query[r - 1].push((1, i));
}
let mut seg = SegmentTreePURQ::new(n + 1, Mat::one(), |a, b| *a * *b);
let mut map = Map::<usize, usize>::new();
for (i, mut p) in query.into_iter().enumerate() {
p.sort();
let mut mat = Mat::one();
for (op, x) in p {
if op == 0 {
let k = (1usize..).find(|k| map.values().all(|v| *v != *k)).unwrap();
map.insert(x, k);
let mut trans = Mat::one();
trans[k][k] = V::zero();
trans[0][k] = V(item[x].2);
mat = mat * trans;
} else {
let k = map.remove(&x).unwrap();
let mut trans = Mat::one();
trans[k][k] = V::zero();
trans[k][0] = V::one();
mat = mat * trans;
}
}
seg.update_tmp(i, mat);
}
seg.update_all();
let out = std::io::stdout();
let mut out = std::io::BufWriter::new(out.lock());
for (mut a, mut b) in ask {
if item[a].1 > item[b].0 {
std::mem::swap(&mut a, &mut b);
}
if item[a].1 > item[b].0 {
writeln!(out, "-1").ok();
} else {
let mut p = Matrix::<V, 1, 6>::zero();
p[0][0] = V::one();
seg.find_left(0, item[a].0, |v| p = p * *v);
let mut q = Matrix::<V, 1, 6>::zero();
q[0][0] = p[0][0];
p = q;
seg.find_left(item[a].1, item[b].0, |v| p = p * *v);
let mut q = Matrix::<V, 1, 6>::zero();
q[0][0] = p[0][0];
p = q;
seg.find_left(item[b].1, n + 1, |v| p = p * *v);
let ans = p[0][0].0 + item[a].2 + item[b].2;
writeln!(out, "{}", ans).ok();
}
}
}
type Mat = Matrix<V, 6, 6>;
const INF: i64 = 10i64.pow(18);
#[derive(Clone, Copy)]
struct V(i64);
impl Add for V {
type Output = V;
fn add(self, rhs: Self) -> Self {
V(self.0.max(rhs.0))
}
}
impl Mul for V {
type Output = V;
fn mul(self, rhs: Self) -> Self {
V((-INF).max(self.0 + rhs.0))
}
}
impl Zero for V {
fn zero() -> Self {
V(-INF)
}
fn is_zero(&self) -> bool {
self.0 == -INF
}
}
impl One for V {
fn one() -> Self {
V(0)
}
fn is_one(&self) -> bool {
self.0 == 0
}
}
/*
6*6行列で計算はできるが間に合う？
4sec, N,Q <= 2*10^5
216N + Q 36logN
信じてみる
*/
// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let 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_export]
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_export]
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, bytes) => {
read_value!($iter, String).bytes().collect::<Vec<u8>>()
};
($iter:expr, usize1) => {
read_value!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
// ---------- end input macro ----------
// ---------- begin segment tree Point Update Range Query ----------
pub struct SegmentTreePURQ<T, F> {
n: usize,
size: usize,
data: Vec<T>,
e: T,
op: F,
}
impl<T, F> SegmentTreePURQ<T, F>
where
T: Clone,
F: Fn(&T, &T) -> T,
{
pub fn new(n: usize, e: T, op: F) -> Self {
assert!(n > 0);
let size = n.next_power_of_two();
let data = vec![e.clone(); 2 * size];
SegmentTreePURQ {
n,
size,
data,
e,
op,
}
}
pub fn update_tmp(&mut self, x: usize, v: T) {
assert!(x < self.n);
self.data[x + self.size] = v;
}
pub fn update_all(&mut self) {
for i in (1..self.size).rev() {
self.data[i] = (self.op)(&self.data[2 * i], &self.data[2 * i + 1]);
}
}
pub fn update(&mut self, x: usize, v: T) {
assert!(x < self.n);
let mut x = x + self.size;
self.data[x] = v;
x >>= 1;
while x > 0 {
self.data[x] = (self.op)(&self.data[2 * x], &self.data[2 * x + 1]);
x >>= 1;
}
}
pub fn find(&self, l: usize, r: usize) -> T {
assert!(l <= r && r <= self.n);
if l == r {
return self.e.clone();
}
let mut l = self.size + l;
let mut r = self.size + r;
let mut x = self.e.clone();
let mut y = self.e.clone();
while l < r {
if l & 1 == 1 {
x = (self.op)(&x, &self.data[l]);
l += 1;
}
if r & 1 == 1 {
r -= 1;
y = (self.op)(&self.data[r], &y);
}
l >>= 1;
r >>= 1;
}
(self.op)(&x, &y)
}
pub fn find_left<P>(&self, l: usize, r: usize, mut f: P)
where
P: FnMut(&T),
{
assert!(l <= r && r <= self.n);
if l == r {
return;
}
let mut l = self.size + l;
let mut r = self.size + r;
let mut bit = 0;
while l < r {
if l & 1 == 1 {
f(&self.data[l]);
l += 1;
}
if r & 1 == 1 {
bit |= 1;
r -= 1;
}
l >>= 1;
r >>= 1;
bit <<= 1;
}
while bit > 0 {
bit >>= 1;
r <<= 1;
if bit & 1 == 1 {
f(&self.data[r]);
r += 1;
bit -= 1;
}
}
}
pub fn max_right<P>(&self, l: usize, f: P) -> usize
where
P: Fn(&T) -> bool,
{
assert!(l <= self.n);
assert!(f(&self.e));
if l == self.n {
return self.n;
}
let mut l = l + self.size;
let mut sum = self.e.clone();
while {
l >>= l.trailing_zeros();
let v = (self.op)(&sum, &self.data[l]);
if !f(&v) {
while l < self.size {
l <<= 1;
let v = (self.op)(&sum, &self.data[l]);
if f(&v) {
sum = v;
l += 1;
}
}
return l - self.size;
}
sum = v;
l += 1;
l.count_ones() > 1
} {}
self.n
}
pub fn min_left<P>(&self, r: usize, f: P) -> usize
where
P: Fn(&T) -> bool,
{
assert!(r <= self.n);
assert!(f(&self.e));
if r == 0 {
return 0;
}
let mut r = r + self.size;
let mut sum = self.e.clone();
while {
r -= 1;
while r > 1 && r & 1 == 1 {
r >>= 1;
}
let v = (self.op)(&self.data[r], &sum);
if !f(&v) {
while r < self.size {
r = 2 * r + 1;
let v = (self.op)(&self.data[r], &sum);
if f(&v) {
sum = v;
r -= 1;
}
}
return r + 1 - self.size;
}
sum = v;
(r & (!r + 1)) != r
} {}
0
}
}
// ---------- end segment tree Point Update Range Query ----------
// ---------- begin const matrix ----------
#[derive(Clone, Copy, Debug)]
pub struct Matrix<T, const R: usize, const C: usize>([[T; C]; R]);
impl<T, const R: usize, const C: usize> Matrix<T, R, C> {
pub fn new(a: [[T; C]; R]) -> Self {
Self(a)
}
pub fn swap_row(&mut self, x: usize, y: usize) {
assert!(x < R && y < R);
self.0.swap(x, y);
}
pub fn swap_col(&mut self, x: usize, y: usize) {
assert!(x < C && y < C);
for mat in self.iter_mut() {
mat.swap(x, y);
}
}
}
impl<T, const R: usize, const C: usize> Matrix<T, R, C>
where
T: Mul<Output = T> + Copy,
{
pub fn scalar(&self, k: T) -> Self {
let mut res = *self;
for a in res.iter_mut().flatten() {
*a = *a * k;
}
res
}
}
impl<T, const R: usize, const C: usize> Zero for Matrix<T, R, C>
where
T: Zero + Copy,
{
fn zero() -> Self {
Self::new([[T::zero(); C]; R])
}
fn is_zero(&self) -> bool {
self.iter().flatten().all(|a| a.is_zero())
}
}
impl<T, const N: usize> One for Matrix<T, N, N>
where
T: Zero + One + Copy,
{
fn one() -> Self {
let mut res = Self::zero();
for (i, a) in res.iter_mut().enumerate() {
a[i] = T::one();
}
res
}
fn is_one(&self) -> bool {
self.iter().enumerate().all(|(i, a)| {
a.iter()
.enumerate()
.all(|(j, a)| (i == j && a.is_one()) || (i != j && a.is_zero()))
})
}
}
impl<T, const R: usize, const C: usize> AddAssign for Matrix<T, R, C>
where
T: Add<Output = T> + Copy,
{
fn add_assign(&mut self, rhs: Self) {
for (a, b) in self.iter_mut().zip(rhs.iter()) {
for (a, b) in a.iter_mut().zip(b.iter()) {
*a = *a + *b;
}
}
}
}
impl<T, const R: usize, const C: usize> SubAssign for Matrix<T, R, C>
where
T: Sub<Output = T> + Copy,
{
fn sub_assign(&mut self, rhs: Self) {
for (a, b) in self.iter_mut().zip(rhs.iter()) {
for (a, b) in a.iter_mut().zip(b.iter()) {
*a = *a - *b;
}
}
}
}
impl<T, const R: usize, const C: usize> Add for Matrix<T, R, C>
where
T: Add<Output = T> + Copy,
{
type Output = Self;
fn add(mut self, rhs: Self) -> Self::Output {
self += rhs;
self
}
}
impl<T, const R: usize, const C: usize> Sub for Matrix<T, R, C>
where
T: Sub<Output = T> + Copy,
{
type Output = Self;
fn sub(mut self, rhs: Self) -> Self::Output {
self -= rhs;
self
}
}
impl<T, const ROW: usize, const COL: usize> Matrix<T, ROW, COL>
where
T: Zero + Mul<Output = T> + Copy,
{
pub fn matmul<const NCOL: usize>(&self, rhs: &Matrix<T, COL, NCOL>) -> Matrix<T, ROW, NCOL> {
let mut res = Matrix::<T, ROW, NCOL>::zero();
for (res, a) in res.iter_mut().zip(self.iter()) {
for (a, b) in a.iter().zip(rhs.iter()) {
for (res, b) in res.iter_mut().zip(b.iter()) {
*res = *res + *a * *b;
}
}
}
res
}
}
impl<T, const ROW: usize, const COL: usize, const MID: usize> Mul<Matrix<T, MID, COL>>
for Matrix<T, ROW, MID>
where
T: Zero + Mul<Output = T> + Copy,
{
type Output = Matrix<T, ROW, COL>;
fn mul(self, rhs: Matrix<T, MID, COL>) -> Self::Output {
self.matmul(&rhs)
}
}
impl<T, const R: usize, const C: usize> MulAssign<Matrix<T, C, C>> for Matrix<T, R, C>
where
T: Zero + Mul<Output = T> + Copy,
{
fn mul_assign(&mut self, rhs: Matrix<T, C, C>) {
*self = self.matmul(&rhs);
}
}
impl<T, const R: usize, const C: usize> Deref for Matrix<T, R, C> {
type Target = [[T; C]; R];
fn deref(&self) -> &Self::Target {
&self.0
}
}
impl<T, const R: usize, const C: usize> DerefMut for Matrix<T, R, C> {
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.0
}
}
// ---------- end const matrix ----------
// ---------- begin trait ----------
use std::ops::*;
pub trait Zero: Sized + Add<Self, Output = Self> {
fn zero() -> Self;
fn is_zero(&self) -> bool;
}
pub trait One: Sized + Mul<Self, Output = Self> {
fn one() -> Self;
fn is_one(&self) -> bool;
}
pub trait Group: Zero + Sub<Output = Self> + Neg<Output = Self> {}
pub trait SemiRing: Zero + One {}
pub trait Ring: SemiRing + Group {}
pub trait Field: Ring + Div<Output = Self> {}
impl<T> Group for T where T: Zero + Sub<Output = Self> + Neg<Output = Self> {}
impl<T> SemiRing for T where T: Zero + One {}
impl<T> Ring for T where T: SemiRing + Group {}
impl<T> Field for T where T: Ring + Div<Output = Self> {}
pub fn zero<T: Zero>() -> T {
T::zero()
}
pub fn one<T: One>() -> T {
T::one()
}
pub fn pow<T: One + Clone>(mut r: T, mut n: usize) -> T {
let mut t = one();
while n > 0 {
if n & 1 == 1 {
t = t * r.clone();
}
r = r.clone() * r;
n >>= 1;
}
t
}
pub fn pow_sum<T: SemiRing + Clone>(mut r: T, mut n: usize) -> T {
let mut ans = T::zero();
let mut sum = T::one();
while n > 0 {
if n & 1 == 1 {
ans = ans * r.clone() + sum.clone();
}
sum = sum * (T::one() + r.clone());
r = r.clone() * r;
n >>= 1;
}
ans
}
// ---------- end trait ----------