atcoder.jp
use std::collections::{BTreeMap, BinaryHeap, VecDeque};
fn main() {
let s = std::io::stdin();
let mut sc = Scanner { stdin: s.lock() };
let n: usize = sc.read();
let mut graph = vec![vec![]; (1 << (n + 1)) - 1];
let mut inverse = vec![vec![]; (1 << (n + 1)) - 1];
for i in 0..((1 << n) - 1) {
graph[i].push(i * 2 + 1);
graph[i].push(i * 2 + 2);
inverse[i * 2 + 1].push(i);
inverse[i * 2 + 2].push(i);
}
let v: Vec<u64> = sc.vec(1 << n);
let count = v.into_iter().fold(BTreeMap::new(), |mut map, v| {
*map.entry(v).or_insert(0) += 1;
map
});
let mut values = vec![0; graph.len()];
let mut heap = BinaryHeap::new();
heap.push((1 << n, 0));
for (value, count) in count.into_iter().rev() {
if heap.len() < count {
println!("No");
return;
}
let vs = (0..count).map(|_| heap.pop().unwrap()).collect::<Vec<_>>();
for (mut size, mut cur) in vs.into_iter() {
loop {
values[cur] = value;
if graph[cur].is_empty() {
break;
}
heap.push((size / 2, graph[cur][1]));
cur = graph[cur][0];
size /= 2;
}
}
}
println!("Yes");
}
fn get_min_leaf(root: usize, graph: &Vec<Vec<usize>>) -> usize {
if graph[root].is_empty() {
root
} else {
get_min_leaf(graph[root][0], graph)
}
}
pub struct Scanner<R> {
stdin: R,
}
impl<R: std::io::Read> Scanner<R> {
pub fn read<T: std::str::FromStr>(&mut self) -> T {
use std::io::Read;
let buf = self
.stdin
.by_ref()
.bytes()
.map(|b| b.unwrap())
.skip_while(|&b| b == b' ' || b == b'\n')
.take_while(|&b| b != b' ' && b != b'\n')
.collect::<Vec<_>>();
unsafe { std::str::from_utf8_unchecked(&buf) }
.parse()
.ok()
.expect("Parse error.")
}
pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
(0..n).map(|_| self.read()).collect()
}
pub fn chars(&mut self) -> Vec<char> {
self.read::<String>().chars().collect()
}
}
atcoder.jp
fn main() {
let s = std::io::stdin();
let mut sc = Scanner { stdin: s.lock() };
let n: usize = sc.read();
let mut v: Vec<_> = (0..n)
.map(|_| (sc.read::<f64>(), sc.read::<f64>()))
.collect();
v.sort_by(|&(x1, y1), &(x2, y2)| y1.atan2(x1).partial_cmp(&y2.atan2(x2)).unwrap());
let tmp = v.clone();
v.extend(tmp);
let mut ans = 0.0;
for head in 0..n {
for tail in head..(head + n) {
let (x, y) = (head..(tail + 1))
.map(|i| v[i])
.fold((0.0, 0.0), |(x, y), (vx, vy)| (x + vx, y + vy));
update_max(&mut ans, x * x + y * y);
}
}
println!("{}", ans.sqrt());
}
fn update_max<T: PartialOrd>(a: &mut T, b: T) {
if *a < b {
*a = b;
}
}
pub struct Scanner<R> {
stdin: R,
}
impl<R: std::io::Read> Scanner<R> {
pub fn read<T: std::str::FromStr>(&mut self) -> T {
use std::io::Read;
let buf = self
.stdin
.by_ref()
.bytes()
.map(|b| b.unwrap())
.skip_while(|&b| b == b' ' || b == b'\n')
.take_while(|&b| b != b' ' && b != b'\n')
.collect::<Vec<_>>();
unsafe { std::str::from_utf8_unchecked(&buf) }
.parse()
.ok()
.expect("Parse error.")
}
pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
(0..n).map(|_| self.read()).collect()
}
pub fn chars(&mut self) -> Vec<char> {
self.read::<String>().chars().collect()
}
}
atcoder.jp
use std::collections::{BTreeMap, BTreeSet};
fn main() {
let s = std::io::stdin();
let mut sc = Scanner { stdin: s.lock() };
let n = sc.read();
let a: Vec<i64> = sc.vec(n);
let mut ok = 0;
let mut ng = 1e10 as i64;
while ng - ok > 1 {
let x = (ng + ok) / 2;
let a = a
.iter()
.map(|&a| if a >= x { 1 } else { -1 })
.collect::<Vec<i64>>();
let mut acc = vec![0; n + 1];
for i in 0..n {
acc[i + 1] = acc[i] + a[i];
}
let map = acc
.iter()
.cloned()
.collect::<BTreeSet<_>>()
.into_iter()
.enumerate()
.map(|(i, v)| (v, i))
.collect::<BTreeMap<_, _>>();
let acc = acc
.into_iter()
.map(|v| *map.get(&v).unwrap())
.collect::<Vec<_>>();
let m = map.len();
let mut bit = fenwick_tree::FenwickTree::new(m, 0);
let mut negative_segments = 0;
for i in 0..(n + 1) {
negative_segments += i - bit.sum_one(acc[i] + 1);
bit.add(acc[i], 1);
}
if negative_segments * 2 > (n + 1) * n / 2 {
ng = x;
} else {
ok = x;
}
}
println!("{}", ok);
}
pub mod fenwick_tree {
use std::ops::{AddAssign, Sub};
/// `FenwickTree` is a data structure that can efficiently update elements
/// and calculate prefix sums in a table of numbers.
/// [https://en.wikipedia.org/wiki/Fenwick_tree](https://en.wikipedia.org/wiki/Fenwick_tree)
pub struct FenwickTree<T> {
n: usize,
data: Vec<T>,
init: T,
}
impl<T: Copy + AddAssign + Sub<Output = T>> FenwickTree<T> {
/// Constructs a new `FenwickTree`. The size of `FenwickTree` should be specified by `size`.
pub fn new(size: usize, init: T) -> FenwickTree<T> {
FenwickTree {
n: size + 1,
data: vec![init; size + 1],
init: init,
}
}
pub fn add(&mut self, k: usize, value: T) {
let mut x = k;
while x < self.n {
self.data[x] += value;
x |= x + 1;
}
}
/// Returns a sum of range `[l, r)`
pub fn sum(&self, l: usize, r: usize) -> T {
self.sum_one(r) - self.sum_one(l)
}
/// Returns a sum of range `[0, k)`
pub fn sum_one(&self, k: usize) -> T {
assert!(k < self.n, "k={} n={}", k, self.n);
let mut result = self.init;
let mut x = k as i32 - 1;
while x >= 0 {
result += self.data[x as usize];
x = (x & (x + 1)) - 1;
}
result
}
}
}
pub struct Scanner<R> {
stdin: R,
}
impl<R: std::io::Read> Scanner<R> {
pub fn read<T: std::str::FromStr>(&mut self) -> T {
use std::io::Read;
let buf = self
.stdin
.by_ref()
.bytes()
.map(|b| b.unwrap())
.skip_while(|&b| b == b' ' || b == b'\n')
.take_while(|&b| b != b' ' && b != b'\n')
.collect::<Vec<_>>();
unsafe { std::str::from_utf8_unchecked(&buf) }
.parse()
.ok()
.expect("Parse error.")
}
pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
(0..n).map(|_| self.read()).collect()
}
pub fn chars(&mut self) -> Vec<char> {
self.read::<String>().chars().collect()
}
}
atcoder.jp
fn main() {
let s = std::io::stdin();
let mut sc = Scanner { stdin: s.lock() };
let n: usize = sc.read();
let h: usize = sc.read();
let w: usize = sc.read();
let mut uf = UnionFind::new(h + w);
let mut edges = vec![];
for _ in 0..n {
let row = sc.read::<usize>() - 1;
let col = sc.read::<usize>() - 1;
let value: u64 = sc.read();
edges.push((value, row, col + h));
}
edges.sort();
let mut ans = 0;
for (value, row, col) in edges.into_iter().rev() {
let x = uf.find(row);
let y = uf.find(col);
if x != y {
if uf.sizes[x] + uf.sizes[y] >= uf.edge_count[x] + uf.edge_count[y] + 1 {
uf.unite(x, y);
ans += value;
}
} else if uf.sizes[x] > uf.edge_count[x] {
uf.edge_count[x] += 1;
ans += value;
}
}
println!("{}", ans);
}
pub struct UnionFind {
parent: Vec<usize>,
sizes: Vec<usize>,
size: usize,
edge_count: Vec<usize>,
}
impl UnionFind {
pub fn new(n: usize) -> UnionFind {
UnionFind {
parent: (0..n).map(|i| i).collect::<Vec<usize>>(),
sizes: vec![1; n],
size: n,
edge_count: vec![0; n],
}
}
pub fn find(&mut self, x: usize) -> usize {
if x == self.parent[x] {
x
} else {
let px = self.parent[x];
self.parent[x] = self.find(px);
self.parent[x]
}
}
pub fn unite(&mut self, x: usize, y: usize) -> bool {
let parent_x = self.find(x);
let parent_y = self.find(y);
if parent_x == parent_y {
return false;
}
let (large, small) = if self.sizes[parent_x] < self.sizes[parent_y] {
(parent_y, parent_x)
} else {
(parent_x, parent_y)
};
self.parent[small] = large;
self.sizes[large] += self.sizes[small];
self.sizes[small] = 0;
self.edge_count[large] += self.edge_count[small] + 1;
self.edge_count[small] = 0;
self.size -= 1;
return true;
}
}
pub struct Scanner<R> {
stdin: R,
}
impl<R: std::io::Read> Scanner<R> {
pub fn read<T: std::str::FromStr>(&mut self) -> T {
use std::io::Read;
let buf = self
.stdin
.by_ref()
.bytes()
.map(|b| b.unwrap())
.skip_while(|&b| b == b' ' || b == b'\n')
.take_while(|&b| b != b' ' && b != b'\n')
.collect::<Vec<_>>();
unsafe { std::str::from_utf8_unchecked(&buf) }
.parse()
.ok()
.expect("Parse error.")
}
pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
(0..n).map(|_| self.read()).collect()
}
pub fn chars(&mut self) -> Vec<char> {
self.read::<String>().chars().collect()
}
}
atcoder.jp
fn main() {
let s = std::io::stdin();
let mut sc = Scanner { stdin: s.lock() };
let n: usize = sc.read();
let k: usize = sc.read();
let power: Vec<i64> = sc.vec(n);
if solve(&power, k) {
println!("Yes");
} else {
println!("No");
}
}
fn solve(power: &Vec<i64>, k: usize) -> bool {
let n = power.len();
let mut acc_a = vec![0; n + 1];
let mut acc_b = vec![0; n + 1];
let mut acc_c = vec![0; n + 1];
for i in 0..n {
let pi = i as i64;
let damage = acc_a[i] * pi * pi + acc_b[i] * pi + acc_c[i];
if damage > power[i] {
return false;
}
if i + k + k - 1 > n && damage != power[i] {
return false;
}
if damage < power[i] {
let remain = power[i] - damage;
let hit = i + k - 1;
acc_a[i] += remain;
acc_a[hit + k] -= remain;
let x = hit as i64 - k as i64;
let y = k as i64 + hit as i64;
acc_b[i] += -remain * 2 * x;
acc_b[hit + 1] -= -remain * 2 * x;
acc_b[hit + 1] += -remain * 2 * y;
acc_b[hit + k] -= -remain * 2 * y;
acc_c[i] += remain * x * x;
acc_c[hit + 1] -= remain * x * x;
acc_c[hit + 1] += remain * y * y;
acc_c[hit + k] -= remain * y * y;
if acc_b[hit + 1].abs() > 1e15 as i64
|| acc_b[hit + k].abs() > 1e15 as i64
|| acc_c[hit + 1].abs() > 1e15 as i64
|| acc_c[hit + k].abs() > 1e15 as i64
{
return false;
}
}
acc_a[i + 1] += acc_a[i];
acc_b[i + 1] += acc_b[i];
acc_c[i + 1] += acc_c[i];
}
true
}
pub struct Scanner<R> {
stdin: R,
}
impl<R: std::io::Read> Scanner<R> {
pub fn read<T: std::str::FromStr>(&mut self) -> T {
use std::io::Read;
let buf = self
.stdin
.by_ref()
.bytes()
.map(|b| b.unwrap())
.skip_while(|&b| b == b' ' || b == b'\n')
.take_while(|&b| b != b' ' && b != b'\n')
.collect::<Vec<_>>();
unsafe { std::str::from_utf8_unchecked(&buf) }
.parse()
.ok()
.expect("Parse error.")
}
pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
(0..n).map(|_| self.read()).collect()
}
pub fn chars(&mut self) -> Vec<char> {
self.read::<String>().chars().collect()
}
}
