Codeforces 1060G. Balls and Pockets

题意

有一个从 \(0\) 到 \(\infty\) 的序列，第 \(a_1,a_2,\dotsc,a_n\) 个位置上各有一个口袋

每秒每个口袋会吃掉当前位置上的数，较大的数会向较小的方向移动以填补空位

\(m\) 次询问在 \(k_i\) 秒后一个位置 \(x_i\) 上的数是什么

\(a_1< a_2< \cdots< a_n\)

\(n,m\le 10^5, a_i,k_i,x_i\le 10^9\)

zx2003说多 log 过不去，不然就去写了

Codeforces 1034D

题意

你有 \(n\) 个区间 \([a_i, b_i]\)，定义区间的区间 \([l,r]\) 的价值是第 \(l\) 个区间到第 \(r\) 个区间的并的总长度

你需要找出 \(k\) 个不同的区间的区间，使得它们的总价值最大

输出总价值

\(1\le n \le 3 * 10^5,1 \le k \le \min\{\frac{n(n+1)}{2},10^9\}\)