結果
| 問題 |
No.1625 三角形の質問
|
| ユーザー |
 akiradeveloper
|
| 提出日時 | 2021-07-27 11:15:25 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 3,499 ms / 6,000 ms |
| コード長 | 15,971 bytes |
| コンパイル時間 | 15,924 ms |
| コンパイル使用メモリ | 401,292 KB |
| 実行使用メモリ | 200,592 KB |
| 最終ジャッジ日時 | 2024-07-23 08:16:41 |
| 合計ジャッジ時間 | 63,803 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 19 |
コンパイルメッセージ
warning: unused variable: `i`
--> src/main.rs:160:9
|
160 | for i in 0..q {
| ^ help: if this is intentional, prefix it with an underscore: `_i`
|
= note: `#[warn(unused_variables)]` on by default
warning: unused variable: `x`
--> src/main.rs:194:23
|
194 | Q::Q1(l,r,x) => {
| ^ help: if this is intentional, prefix it with an underscore: `_x`
warning: unused variable: `x`
--> src/main.rs:215:23
|
215 | Q::Q1(l,r,x) => {
| ^ help: if this is intentional, prefix it with an underscore: `_x`
warning: field `dcmp` is never read
--> src/main.rs:445:5
|
443 | struct CoordCompression {
| ---------------- field in this struct
444 | comp: std::collections::HashMap<i64, usize>,
445 | dcmp: std::collections::HashMap<usize, i64>,
| ^^^^
|
= note: `#[warn(dead_code)]` on by default
warning: method `decompress` is never used
--> src/main.rs:470:12
|
447 | impl CoordCompression {
| --------------------- method in this implementation
...
470 | pub fn decompress(&self, x: usize) -> i64 {
| ^^^^^^^^^^
warning: variable `T` should have a snake case name
--> src/main.rs:149:13
|
149 | let mut T = vec![];
| ^ help: convert the identifier to snake case: `t`
|
= note: `#[warn(non_snake_case)]` on by default
warning: variable `Q` should have a snake case name
--> src/main.rs:159:13
|
159 | let mut Q = vec![];
| ^ help: convert the identifier to snake case: `q`
warning: variable `X` should have a snake case name
--> src/main.rs:186:13
|
186 | let mut X = vec![];
| ^ help: convert the identifier to snake case (notice the capitalization): `x`
warning: variable `Y` should have a snake case name
--> src/main.rs:187:13
|
187 | let mut Y = vec![];
| ^ help: convert the identifier to sn
ソースコード
#[doc = " https://github.com/akiradeveloper/rust-comp-snippets"]
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::iter::FromIterator;
#[macro_export]
macro_rules ! chmax { ( $ x : expr , $ ( $ v : expr ) ,+ ) => { $ ( $ x = std :: cmp :: max ( $ x ,$ v ) ; ) + } ; }
#[macro_export]
macro_rules ! chmin { ( $ x : expr , $ ( $ v : expr ) ,+ ) => { $ ( $ x = std :: cmp :: min ( $ x ,$ v ) ; ) + } ; }
#[macro_export]
macro_rules ! max { ( $ x : expr ) => ( $ x ) ; ( $ x : expr , $ ( $ xs : expr ) ,+ ) => { std :: cmp :: max ( $ x , max ! ( $ ( $ xs ) ,+ ) ) } ; }
#[macro_export]
macro_rules ! min { ( $ x : expr ) => ( $ x ) ; ( $ x : expr , $ ( $ xs : expr ) ,+ ) => { std :: cmp :: min ( $ x , min ! ( $ ( $ xs ) ,+ ) ) } ; }
#[macro_export]
macro_rules ! dvec { ( $ t : expr ; $ len : expr ) => { vec ! [ $ t ; $ len ] } ; ( $ t : expr ; $ len : expr , $ ( $ rest : expr ) ,* ) => { vec ! [ dvec ! ( $ t ; $ ( $ rest ) ,* ) ; $ len ] } ; }
#[macro_export]
macro_rules ! cfor { ( ; $ ( $ rest : tt ) * ) => { cfor ! ( ( ) ; $ ( $ rest ) * ) } ; ( $ ( $ init : stmt ) ,+; ; $ ( $ rest : tt ) * ) => { cfor ! ( $ ( $ init ) ,+; ! false ; $ ( $ rest ) * ) } ; ( $ ( $ init : stmt ) ,+; $ cond : expr ; ; $ body : block ) => { cfor ! { $ ( $ init ) ,+; $ cond ; ( ) ; $ body } } ; ( $ ( $ init : stmt ) ,+; $ cond : expr ; $ ( $ step : expr ) ,+; $ body : block ) => { { $ ( $ init ; ) + while $ cond { let mut _first = true ; let mut _continue = false ; loop { if ! _first { _continue = true ; break } _first = false ; $ body } if ! _continue { break } $ ( $ step ; ) + } } } ; }
#[doc = " main"]
#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};
#[macro_export]
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut parser = Parser :: from_str ( $ s ) ; input_inner ! { parser , $ ( $ r ) * } } ; ( parser = $ parser : ident , $ ( $ r : tt ) * ) => { input_inner ! { $ parser , $ ( $ r ) * } } ; ( new_stdin_parser = $ parser : ident , $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let reader = std :: io :: BufReader :: new ( stdin . lock ( ) ) ; let mut $ parser = Parser :: new ( reader ) ; input_inner ! { $ parser , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { input ! { new_stdin_parser = parser , $ ( $ r ) * } } ; }
#[macro_export]
macro_rules ! input_inner { ( $ parser : ident ) => { } ; ( $ parser : ident , ) => { } ; ( $ parser : ident , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ parser , $ t ) ; input_inner ! { $ parser $ ( $ r ) * } } ; }
#[macro_export]
macro_rules ! read_value { ( $ parser : ident , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ parser , $ t ) ) ,* ) } ; ( $ parser : ident , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ parser , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ parser : ident , chars ) => { read_value ! ( $ parser , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ parser : ident , usize1 ) => { read_value ! ( $ parser , usize ) - 1 } ; ( $ parser : ident , $ t : ty ) => { $ parser . next ::<$ t > ( ) . expect ( "Parse error" ) } ; }
use std::io;
use std::io::BufRead;
use std::str;
pub struct Parser<R> {
reader: R,
buf: Vec<u8>,
pos: usize,
}
impl Parser<io::Empty> {
pub fn from_str(s: &str) -> Parser<io::Empty> {
Parser {
reader: io::empty(),
buf: s.as_bytes().to_vec(),
pos: 0,
}
}
}
impl<R: BufRead> Parser<R> {
pub fn new(reader: R) -> Parser<R> {
Parser {
reader: reader,
buf: vec![],
pos: 0,
}
}
pub fn update_buf(&mut self) {
self.buf.clear();
self.pos = 0;
loop {
let (len, complete) = {
let buf2 = self.reader.fill_buf().unwrap();
self.buf.extend_from_slice(buf2);
let len = buf2.len();
if len == 0 {
break;
}
(len, buf2[len - 1] <= 0x20)
};
self.reader.consume(len);
if complete {
break;
}
}
}
pub fn next<T: str::FromStr>(&mut self) -> Result<T, T::Err> {
loop {
let mut begin = self.pos;
while begin < self.buf.len() && (self.buf[begin] <= 0x20) {
begin += 1;
}
let mut end = begin;
while end < self.buf.len() && (self.buf[end] > 0x20) {
end += 1;
}
if begin != self.buf.len() {
self.pos = end;
return str::from_utf8(&self.buf[begin..end]).unwrap().parse::<T>();
} else {
self.update_buf();
}
}
}
}
#[allow(unused_macros)]
macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) ; } }
#[doc = " https://github.com/hatoo/competitive-rust-snippets"]
const BIG_STACK_SIZE: bool = true;
#[allow(dead_code)]
fn main() {
use std::thread;
if BIG_STACK_SIZE {
thread::Builder::new()
.stack_size(32 * 1024 * 1024)
.name("solve".into())
.spawn(solve)
.unwrap()
.join()
.unwrap();
} else {
solve();
}
}
enum Q {
Q1(i64,i64,i64),
Q2(i64,i64),
}
struct Tri {
x0:i64,y0:i64,
x1:i64,y1:i64,
x2:i64,y2:i64,
}
impl Tri {
fn area(&self) -> i64 {
let a = (self.x1-self.x0, self.y1-self.y0);
let b = (self.x2-self.x0, self.y2-self.y0);
i64::abs(a.0*b.1 - a.1*b.0)
}
fn left(&self) -> i64 {
let mut v = 1<<60;
chmin!(v,self.x0);
chmin!(v,self.x1);
chmin!(v,self.x2);
v
}
fn right(&self) -> i64 {
let mut v = 0;
chmax!(v,self.x0);
chmax!(v,self.x1);
chmax!(v,self.x2);
v
}
}
fn solve() {
let out = stdout();
let mut out = BufWriter::new(out.lock());
input!{
new_stdin_parser=parser,
n:usize,q:usize,
tris:[(i64,i64,i64,i64,i64,i64);n],
}
let mut T = vec![];
for tri in tris {
let tri = Tri {
x0:tri.0, y0:tri.1,
x1:tri.2, y1:tri.3,
x2:tri.4, y2:tri.5,
};
T.push((tri.left(), tri.right(), tri.area()));
}
let mut Q = vec![];
for i in 0..q {
input!{
parser=parser,
ty:usize,
}
if ty == 1 {
input!{
parser=parser,
tri:(i64,i64,i64,i64,i64,i64),
}
let tri = Tri {
x0:tri.0, y0:tri.1,
x1:tri.2, y1:tri.3,
x2:tri.4, y2:tri.5,
};
let q = Q::Q1(tri.left(), tri.right(), tri.area());
Q.push(q);
} else {
input!{
parser=parser,
l:i64,r:i64,
}
let q = Q::Q2(l,r);
Q.push(q);
}
}
let mut X = vec![];
let mut Y = vec![];
for t in &T {
X.push(t.0);
Y.push(t.1);
}
for q in &Q {
match q {
Q::Q1(l,r,x) => {
X.push(*l);
Y.push(*r);
},
Q::Q2(l,r) => {
X.push(*l);
Y.push(*r);
}
}
}
let xcomp = CoordCompression::new(&X, 0);
let ycomp = CoordCompression::new(&Y, 0);
let mut xy = vec![vec![]; xcomp.comp.len()];
for t in &T {
let i = xcomp.compress(t.0);
let j = ycomp.compress(t.1);
xy[i].push(j);
}
for q in &Q {
match q {
Q::Q1(l,r,x) => {
let i = xcomp.compress(*l);
let j = ycomp.compress(*r);
xy[i].push(j);
},
Q::Q2(l,r) => {
let i = xcomp.compress(*l);
let j = ycomp.compress(*r);
xy[i].push(j);
}
}
}
let n = xy.len();
let mut seg: SEG2d<MAX> = SEG2d::new(xy);
for t in &T {
let i = xcomp.compress(t.0);
let j = ycomp.compress(t.1);
seg.update(i,j,t.2);
}
for q in &Q {
match q {
Q::Q1(l,r,x) => {
let i = xcomp.compress(*l);
let j = ycomp.compress(*r);
seg.update(i,j,*x);
},
Q::Q2(l,r) => {
let i = xcomp.compress(*l);
let j = ycomp.compress(*r);
let maxv = seg.query(i,n,0,j+1);
writeln!(out,"{}",maxv);
}
}
}
}
pub struct SEG2d<M: Monoid> {
tree: SEGTree,
segs: Vec<SEG<M>>,
index: Vec<Vec<usize>>,
}
impl<M: Monoid> SEG2d<M> {
pub fn new(xy: Vec<Vec<usize>>) -> Self {
let tree = SEGTree::new(xy.len());
let n = xy.len().next_power_of_two();
let mut index = vec![vec![];2*n];
for i in 0..xy.len() {
let mut v = xy[i].clone();
v.sort(); v.dedup();
index[i+n] = v;
}
let mut k = n-1;
while k>=1 {
let l = 2*k;
let r = 2*k+1;
let mut v = vec![];
v.extend_from_slice(&index[l]);
v.extend_from_slice(&index[r]);
v.sort(); v.dedup();
index[k] = v;
k-=1;
}
let mut segs = vec![];
for ii in &index {
let s: SEG<M> = SEG::new(ii.len());
segs.push(s);
}
Self { tree, index, segs }
}
#[doc = " 計算量"]
#[doc = " O(logH logW)"]
pub fn update(&mut self, x: usize, y: usize, v: M::T) {
let nodes = self.tree.update_nodes(x);
for node in nodes {
match node {
SEGNode::Leaf { k } => {
let i = self.index[k].binary_search(&y).unwrap();
self.segs[k].update(i, v.clone());
}
SEGNode::Branch { k, l, r } => {
let mut v = M::id();
if let Ok(il) = self.index[l].binary_search(&y) {
let vl = self.segs[l].get(il);
v = M::op(&v, &vl);
}
if let Ok(ir) = self.index[r].binary_search(&y) {
let vr = self.segs[r].get(ir);
v = M::op(&v, &vr);
}
let i = self.index[k].binary_search(&y).unwrap();
self.segs[k].update(i, v);
}
}
}
}
#[doc = " [x0,x1) x [y0,y1)"]
#[doc = " 計算量"]
#[doc = " O(logH logW)"]
pub fn query(&self, x0: usize, x1: usize, y0: usize, y1: usize) -> M::T {
let nodes = self.tree.query_nodes(x0, x1);
let mut ans = M::id();
for k in nodes {
let l = self.index[k].lower_bound(&y0);
let r = self.index[k].lower_bound(&y1);
let v = self.segs[k].query(l, r);
ans = M::op(&ans, &v);
}
ans
}
}
#[derive(PartialEq, Debug)]
pub enum SEGNode {
Leaf { k: usize },
Branch { k: usize, l: usize, r: usize },
}
pub struct SEGTree {
#[doc = " 葉の数（２の累乗）"]
pub n: usize,
}
impl SEGTree {
pub fn new(n: usize) -> SEGTree {
let n = n.next_power_of_two();
Self { n: n }
}
pub fn update_nodes(&self, i: usize) -> Vec<SEGNode> {
use SEGNode::*;
let mut i = i + self.n;
let mut res = vec![Leaf { k: i }];
while i > 1 {
i >>= 1;
res.push(Branch {
k: i,
l: i * 2,
r: i * 2 + 1,
});
}
res
}
#[doc = " [l,r)"]
pub fn query_nodes(&self, l: usize, r: usize) -> Vec<usize> {
let mut ret = vec![];
let mut l = l + self.n;
let mut r = r + self.n;
while l < r {
if l & 1 > 0 {
ret.push(l);
l += 1;
}
if r & 1 > 0 {
r -= 1;
ret.push(r);
}
l >>= 1;
r >>= 1;
}
// ret.sort();
ret
}
}
struct MAX;
impl Monoid for MAX {
type T = i64;
fn id() -> Self::T {
-1
}
fn op(a: &Self::T, b: &Self::T) -> Self::T {
std::cmp::max(*a, *b)
}
}
#[doc = " フェニック木の一般化"]
#[doc = " "]
#[doc = " 各ノードには最初、idに相当する値が入っている。"]
#[doc = " get i: a[i]を返す"]
#[doc = " update i x: a[i]=x"]
#[doc = " query l r: [l,r)をカバーするノードに対してopを適用したもの"]
#[allow(dead_code)]
pub trait Monoid {
type T: Clone + std::fmt::Debug;
fn id() -> Self::T;
fn op(a: &Self::T, b: &Self::T) -> Self::T;
}
#[allow(dead_code)]
pub struct SEG<M: Monoid> {
pub n: usize,
pub buf: Vec<M::T>,
}
impl<M: Monoid> SEG<M> {
#[allow(dead_code)]
pub fn new(n: usize) -> SEG<M> {
let mut m = 1;
while m < n {
m *= 2;
}
SEG {
n: m,
buf: vec![M::id().clone(); 2 * m],
}
}
#[allow(dead_code)]
pub fn update(&mut self, k: usize, a: M::T) {
let mut k = k + self.n;
self.buf[k] = a;
while k > 1 {
k = k >> 1;
self.buf[k] = M::op(&self.buf[k * 2], &self.buf[k * 2 + 1]);
}
}
#[allow(dead_code)]
pub fn get(&self, k: usize) -> M::T {
self.buf[k + self.n].clone()
}
pub fn do_query(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> M::T {
if r <= a || b <= l {
return M::id();
}
if a <= l && r <= b {
return self.buf[k].clone();
} else {
let vl = self.do_query(a, b, k * 2, l, (l + r) / 2);
let vr = self.do_query(a, b, k * 2 + 1, (l + r) / 2, r);
return M::op(&vl, &vr);
}
}
#[allow(dead_code)]
pub fn query(&self, a: usize, b: usize) -> M::T {
self.do_query(a, b, 1, 0, self.n)
}
}
struct CoordCompression {
comp: std::collections::HashMap<i64, usize>,
dcmp: std::collections::HashMap<usize, i64>,
}
impl CoordCompression {
pub fn new(xs: &[i64], start: usize) -> CoordCompression {
let mut xs = xs.to_owned();
xs.sort();
let mut comp = std::collections::HashMap::new();
let mut dcmp = std::collections::HashMap::new();
let mut acc = start;
for x in xs {
if comp.contains_key(&x) {
continue;
}
comp.insert(x, acc);
dcmp.insert(acc, x);
acc += 1;
}
CoordCompression {
comp: comp,
dcmp: dcmp,
}
}
pub fn compress(&self, x: i64) -> usize {
*self.comp.get(&x).unwrap()
}
pub fn decompress(&self, x: usize) -> i64 {
*self.dcmp.get(&x).unwrap()
}
}
#[doc = " Equivalent to std::lowerbound and std::upperbound in c++"]
pub trait LowerBound<T> {
fn lower_bound(&self, x: &T) -> usize;
fn upper_bound(&self, x: &T) -> usize;
}
impl<T: Ord> LowerBound<T> for [T] {
fn lower_bound(&self, x: &T) -> usize {
let mut low = 0;
let mut high = self.len();
while low != high {
let mid = (low + high) / 2;
match self[mid].cmp(x) {
Ordering::Less => {
low = mid + 1;
}
Ordering::Equal | Ordering::Greater => {
high = mid;
}
}
}
low
}
fn upper_bound(&self, x: &T) -> usize {
let mut low = 0;
let mut high = self.len();
while low != high {
let mid = (low + high) / 2;
match self[mid].cmp(x) {
Ordering::Less | Ordering::Equal => {
low = mid + 1;
}
Ordering::Greater => {
high = mid;
}
}
}
low
}
}