Solution -「ARC 082D」Sandglass
2024-10-20 00:19:05
\(\mathcal{Description}\)
Link.
一个沙漏内共 \(Xg\) 沙,令初始时上半部分为 A,下半部分为 B。沙漏在 \(r_1,r_2,\cdots,r_n\) 时刻会被瞬间翻转。\(q\) 次询问,每次询问给出 \((t,a)\),求初始时 A 有 \(ag\) 沙,\(t\) 时刻时 A 内沙的质量。保证 \(r_{1..n},t_{1..q}\) 升序。
\(n,q\le10^5\)。
\(\mathcal{Solution}\)
显然,随着初始 A 内沙质量的增多,任意时刻下 A 内沙的质量都不会减少。记 \(m(a,t)\) 表示初始 A 有 \(ag\) 沙,\(t\) 时刻时 A 内沙的质量,则应满足 \((\forall t)\left(m(0,t)\le m(a,t)\le m(X,t)\right)\);此外,若存在一个 \(t_0\),使得 \(m(a,t_0)=m(0,t_0)\)(或 \(m(a,t_0)=m(X,t_0)\)),则对于所有 \(t\ge t_0\),都有 \(m(a,t)=m(0,t)\)(或 \(m(a,t)=m(X,t)\))。
据此,维护当前时刻 A 内沙子质量的上下界 \([l,u]\) 以及不考虑上方沙子漏完情况下的 A 内沙子质量 \(x\),若 \(x\in[l,u]\),根据上述性质,不存在沙子漏光的无效时间,\(x\) 就是本次询问答案;否则,取下界或者上界作为答案即可。
复杂度 \(\mathcal O(n+q)\)。
\(\mathcal{Code}\)
/* Clearink */
#include <cstdio>
#include <iostream>
inline int rint () {
int x = 0, f = 1; char s = getchar ();
for ( ; s < '0' || '9' < s; s = getchar () ) f = s == '-' ? -f : f;
for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );
return x * f;
}
template<typename Tp>
inline void wint ( Tp x ) {
if ( x < 0 ) putchar ( '-' ), x = -x;
if ( 9 < x ) wint ( x / 10 );
putchar ( x % 10 ^ '0' );
}
const int MAXN = 1e5;
int X, n, r[MAXN + 5];
int main () {
X = rint (), n = rint ();
for ( int i = 1; i <= n; ++ i ) r[i] = rint ();
int ubound = X, lbound = 0, cur = 0, tid = 1, side = -1;
for ( int q = rint (), t, a; q --; ) {
t = rint (), a = rint ();
for ( ; tid <= n && r[tid] <= t; side *= -1, ++ tid ) {
lbound = std::min ( X, std::max ( 0, lbound + side * ( r[tid] - r[tid - 1] ) ) );
ubound = std::min ( X, std::max ( 0, ubound + side * ( r[tid] - r[tid - 1] ) ) );
cur += side * ( r[tid] - r[tid - 1] );
}
int clb = std::min ( X, std::max ( 0, lbound + side * ( t - r[tid - 1] ) ) );
int cub = std::min ( X, std::max ( 0, ubound + side * ( t - r[tid - 1] ) ) );
int sum = cur + side * ( t - r[tid - 1] );
wint ( std::min ( cub, std::max ( clb, sum + a ) ) ), putchar ( '\n' );
}
return 0;
}
\(\mathcal{Details}\)
一道很巧妙的题。假设 \(a\) 为常数,画出 \(m(a,t)\) 的函数图像,就是一个类似于多段绝对值函数的样子。可以非常直观的理解结论(可是我懒得画 owo)。
最新文章
- html规范
- Linux下的Hello world
- SqlParameter的感悟
- 如何在Mac系统里面更新 Ansible 的 Extra Modules
- linux 中php以及nginx的重启命令
- VS使用技巧(转)
- uva 211(dfs)
- [Stanford 2011] Views 知识点
- Python Counter()计数工具
- 使用Spring Boot快速构建应用
- Android编程动态创建视图View的方法
- MongoDB权限提升漏洞(CVE-2013-4650)
- rpm软件包类型
- 费用流&;网络流模版
- maven排除jar包冲突
- 高分一号计算NDVI
- 通过c++11的condition_variable实现的有最大缓存限制的队列
- asp.net core 依赖注入几种常见情况
- A Tale of Three Apache Spark APIs: RDDs, DataFrames, and Datasets(中英双语)
- Pyenv 安装部署