当前位置:网站首页>CF780G Andryusha and Nervous Barriers
CF780G Andryusha and Nervous Barriers
2022-07-30 13:40:00 【With a cool moon】
CF780G Andryusha and Nervous Barriers
考虑树套树.
One-dimensional maintenance interval column,Another dimension maintains the height of the ball on the column,Make sure the points are correct.
maintenance single point,区间查.
The situation when the scan line height is maintained to each board from large to small.
优化:The interval check is to judge that the minimum height of the interval ball can only pass through the baffle and end.
时间复杂度 O ( n log 2 n ) \mathcal O(n\log^2n) O(nlog2n).
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
#define ha putchar(' ')
#define he putchar('\n')
inline int read() {
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
return x * f;
}
inline void write(int x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + 48);
}
const int _ = 1e5 + 10, mod = 1e9 + 7;
int h, w, n, N;
ll ans[_ << 2];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q[_];
struct abc {
int u, l, r, s;
bool operator < (const abc &t) const {
return u > t.u;
}
} k[_];
void build(int o, int l, int r) {
if (l == r) {
q[l].push({
h + 1, 1});
ans[o] = h + 1;
return;
}
int mid = (l + r) >> 1;
build(o << 1, l, mid), build(o << 1 | 1, mid + 1, r);
ans[o] = min(ans[o << 1], ans[o << 1 | 1]);
}
void upd(int o, int l, int r, int pos, int p, int h) {
if (l == r) {
q[l].push({
h, p});
ans[o] = min(ans[o], (ll)h);
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) upd(o << 1, l, mid, pos, p, h);
else upd(o << 1 | 1, mid + 1, r, pos, p, h);
ans[o] = min(ans[o << 1], ans[o << 1 | 1]);
}
int qry(int o, int l, int r, int L, int R, int h, int s) {
if (ans[o] > h + s) return 0;
if (l == r) {
int res = 0;
while (!q[l].empty() && q[l].top().first <= h + s) {
res = (res + q[l].top().second) % mod;
q[l].pop();
}
ans[o] = q[l].empty() ? 1e10 + 7 : q[l].top().first;
return res;
}
int mid = (l + r) >> 1, res = 0;
if (L <= mid) res = qry(o << 1, l, mid, L, R, h, s);
if (R > mid) res = (res + qry(o << 1 | 1, mid + 1, r, L, R, h, s)) % mod;
ans[o] = min(ans[o << 1], ans[o << 1 | 1]);
return res;
}
signed main() {
h = read(), w = read(), n = read();
for (int i = 1; i <= n; ++i) k[i].u = read(), k[i].l = read(), k[i].r = read(), k[i].s = read();
N = w;
build(1, 1, w);
sort(k + 1, k + n + 1);
for (int i = 1; i <= n; ++i) {
int t = qry(1, 1, w, k[i].l, k[i].r, k[i].u, k[i].s);
N = (N + t) % mod;
if (k[i].l == 1) upd(1, 1, w, k[i].r + 1, (t << 1) % mod, k[i].u);
else if (k[i].r == w) upd(1, 1, w, k[i].l - 1, (t << 1) % mod, k[i].u);
else {
upd(1, 1, w, k[i].l - 1, t, k[i].u);
upd(1, 1, w, k[i].r + 1, t, k[i].u);
}
}
write(N), he;
return 0;
}
边栏推荐
猜你喜欢
如何判断自己是否适合IT行业?方法很简单
腾讯称电竞人才缺口200万;华为鸿蒙3.0正式发布;乐视推行每周工作4天半?...丨黑马头条...
Self-tuning PID self-tuning control 】 【
经典测试面试题集—逻辑推理题
【微信小程序】一文带你搞懂小程序的页面配置和网络数据请求
重保特辑|筑牢第一道防线,云防火墙攻防演练最佳实践
无代码开发平台应用可见权限设置入门教程
程序员修炼之道:务以己任,实则明心——通向务实的最高境界
No-code development platform all application settings introductory tutorial
jsArray数组复制方法性能测试2207292307
随机推荐
434. 字符串中的单词数
Smart pointer implementation conjecture
Parallelized Quick Sort Ideas
“封号斗罗” 程序员修炼之道:通向务实的最高境界
CF338E Optimize!
简单理解精确率(Precision),召回率(Recall),准确率(Accuracy),TP,TN,FP,FN
干货分享:小技巧大用处之Bean管理类工厂多种实现方式
重保特辑|筑牢第一道防线,云防火墙攻防演练最佳实践
【Advanced Mathematics】【7】Double Integral
电池包托盘有进水风险,存在安全隐患,紧急召回52928辆唐DM
Yilian: Activating the Value Potential of Data Elements and Unleashing the Innovation Dividend of SAS SSD
[Go]四、模块和包、流程控制、结构体
R语言筛选时间序列数据的子集(subset time series data)、使用window函数筛选连续日期时间范围内的数据(start参数和end参数分别指定起始和结束时间)
Composer安装方式
BUUCTF刷题十一道(06)
数据中台建设(五):打破企业数据孤岛和提取数据价值
无代码开发平台全部应用设置入门教程
一本通循环结构的程序设计第一章题解(1)
机器学习——特征选择
jsArray array copy method performance test 2207292307