use std::io::{self, Stdin}; use std::str::{self, FromStr}; use std::error::Error; use std::thread; fn exec() { let mut sc = Scanner::new(); let n: usize = sc.ne(); let k: i32 = sc.ne(); let w: Vec = (0..n).map(|_| sc.ne()).collect(); let &ma = w.iter().max().unwrap(); let n = ma as usize; let mut fwt = FenwickTree::new(n + 1, 0i32); for x in w { if x < 0 { let id = (x * -1) as usize; let num = fwt.sum(id + 1) - fwt.sum(id); if num > 0 { fwt.add(id, -1); } } else { let id = x as usize; let num = fwt.sum(n + 1) - fwt.sum(id); if num < k { fwt.add(id, 1); } } } println!("{}", fwt.sum(n + 1)); } struct FenwickTree { zero: T, n: usize, data: Vec, } use std::ops::AddAssign; impl FenwickTree { fn new(n_: usize, z_: T) -> FenwickTree { FenwickTree { zero: z_, n: n_, data: vec![z_; n_], } } //sum of [0, j) fn sum(&self, j: usize) -> T { let mut res = self.zero; let mut x = j as i64 - 1; while x >= 0 { res += self.data[x as usize]; x = (x & (x + 1)) - 1; } res } // add w to a[j] fn add(&mut self, j: usize, w: T) { let mut x = j; while x < self.n { self.data[x] += w; x |= x + 1; } } } fn main() { const DEFAULT_STACK: usize = 16 * 1024 * 1024; let builder = thread::Builder::new(); let th = builder.stack_size(DEFAULT_STACK); let handle = th.spawn(|| { exec(); }).unwrap(); let _ = handle.join(); } #[allow(dead_code)] struct Scanner { stdin: Stdin, id: usize, buf: Vec, } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { stdin: io::stdin(), id: 0, buf: Vec::new(), } } fn next_line(&mut self) -> Option { let mut res = String::new(); match self.stdin.read_line(&mut res) { Ok(0) => return None, Ok(_) => Some(res), Err(why) => panic!("error in read_line: {}", why.description()), } } fn next(&mut self) -> Option { while self.buf.len() == 0 { self.buf = match self.next_line() { Some(r) => { self.id = 0; r.trim().as_bytes().to_owned() } None => return None, }; } let l = self.id; assert!(self.buf[l] != b' '); let n = self.buf.len(); let mut r = l; while r < n && self.buf[r] != b' ' { r += 1; } let res = match str::from_utf8(&self.buf[l..r]).ok().unwrap().parse::() { Ok(s) => Some(s), Err(_) => { panic!("parse error, {:?}", String::from_utf8(self.buf[l..r].to_owned())) } }; while r < n && self.buf[r] == b' ' { r += 1; } if r == n { self.buf.clear(); } else { self.id = r; } res } fn ne(&mut self) -> T { self.next::().unwrap() } }