博客
关于我
P1502 窗口的星星
阅读量:553 次
发布时间:2019-03-09

本文共 1743 字,大约阅读时间需要 5 分钟。

题目链接

代码

#include
#include
#include
#include
using namespace std;typedef pair
PII;const int N = 10010;vector
row;struct Line { int x, y1, y2, v; bool operator < (const Line& l) const { return x == l.x ? v > l.v : x < l.x; }}line[N << 1];struct Node { int l, r, v, lz;}tr[N << 3];inline void eval(Node& t, int k) { t.v += k; t.lz += k;}inline void push_down(int u) { eval(tr[u << 1], tr[u].lz); eval(tr[u << 1 | 1], tr[u].lz); tr[u].lz = 0;}void build(int u, int l, int r) { tr[u] = { l , r , 0, 0}; if (l != r) { int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); }}void modify(int u, int l, int r, int k) { if (l <= tr[u].l && r >= tr[u].r) eval(tr[u], k); else { push_down(u); int mid = tr[u].l + tr[u].r >> 1; if (l <= mid) modify(u << 1, l, r, k); if (r > mid) modify(u << 1 | 1, l, r, k); tr[u].v = tr[u << 1].v > tr[u << 1 | 1].v ? tr[u << 1].v : tr[u << 1 | 1].v; }}int find(int k) { int l = 0, r = row.size() - 1; while (l < r) { int mid = l + r >> 1; if (k <= row[mid]) r = mid; else l = mid + 1; } return l + 1;}int main() { int t; scanf("%d", &t); while (t--) { int n, w, h, ans = 0; scanf("%d%d%d", &n, &w, &h); for (int i = 0; i < n; ++i) { int x, y, v; scanf("%d%d%d", &x, &y, &v); line[i << 1] = { x, y, y + h - 1, v }; line[i << 1 | 1] = { x + w - 1, y, y + h - 1, -v }; row.push_back(y); row.push_back(y + h - 1); } sort(line, line + 2 * n); sort(row.begin(), row.end()); row.erase(unique(row.begin(), row.end()), row.end()); build(1, 1, row.size()); for (int i = 0; i < 2 * n; ++i) { modify(1, find(line[i].y1), find(line[i].y2), line[i].v); ans = ans < tr[1].v ? tr[1].v : ans; } row.clear(); printf("%d\n", ans); } return 0;}

转载地址:http://nmzpz.baihongyu.com/

你可能感兴趣的文章
MAC M1大数据0-1成神篇-25 hadoop高可用搭建
查看>>
mac mysql 进程_Mac平台下启动MySQL到完全终止MySQL----终端八步走
查看>>
Mac OS 12.0.1 如何安装柯美287打印机驱动,刷卡打印
查看>>
MangoDB4.0版本的安装与配置
查看>>
Manjaro 24.1 “Xahea” 发布!具有 KDE Plasma 6.1.5、GNOME 46 和最新的内核增强功能
查看>>
mapping文件目录生成修改
查看>>
MapReduce程序依赖的jar包
查看>>
mariadb multi-source replication(mariadb多主复制)
查看>>
MariaDB的简单使用
查看>>
MaterialForm对tab页进行隐藏
查看>>
Member var and Static var.
查看>>
memcached高速缓存学习笔记001---memcached介绍和安装以及基本使用
查看>>
memcached高速缓存学习笔记003---利用JAVA程序操作memcached crud操作
查看>>
Memcached:Node.js 高性能缓存解决方案
查看>>
memcache、redis原理对比
查看>>
memset初始化高维数组为-1/0
查看>>
Metasploit CGI网关接口渗透测试实战
查看>>
Metasploit Web服务器渗透测试实战
查看>>
MFC模态对话框和非模态对话框
查看>>
Moment.js常见用法总结
查看>>