ACM模版

## 代码

```#include <iostream>
#include <algorithm>
#include <map>

#define lson (root << 1) + 1
#define rson (root << 1) + 2

using namespace std;

const int MAXN = 90002;

struct node1
{
int l, r;
long long max_value, sing_value;
} tree[MAXN << 3];

struct node2
{
double x, y1, y2;
int value;
bool end;
} line[MAXN << 1];

struct sta
{
int x, y, value;
} star[MAXN];

int cnt_l, cnt_d;
long long N, W, H;
double dy[MAXN << 1];
map<double, int> mdi;

bool cmp_1(double a, double b)
{
return a < b;
}

bool cmp_2(const node2 a, const node2 b)
{
if (a.x == b.x)
{
return !a.end;
}
else
{
return a.x < b.x;
}
}

void build_tree(int root, int L, int R)
{
tree[root].l = L;
tree[root].r = R;
tree[root].max_value = 0;
tree[root].sing_value = 0;

if (L != R)
{
int m = (L + R) >> 1;
build_tree(lson, L, m);
build_tree(rson, m + 1, R);
}
}

void add_tree(int root, int L, int R, int c)
{
if (tree[root].l == L && tree[root].r == R)
{
tree[root].sing_value += c;
tree[root].max_value += c;
return ;
}

int m = (tree[root].l + tree[root].r) >> 1;
if (R <= m)
{
}
else if (L >= m + 1)
{
}
else
{
add_tree(rson, m + 1, R, c);
}
tree[root].max_value = max(tree[lson].max_value, tree[rson].max_value)
+ tree[root].sing_value;
}

int main()
{
int L1, R1;
long long ans;
double xx, yy;
while (~scanf("%lld%lld%lld", &N, &W, &H))
{
xx = W / 2.0;
yy = H / 2.0;
mdi.clear();
cnt_l = 0;
cnt_d = 0;
for (int i = 1; i <= N; i++)
{
scanf("%d%d%d", &star[i].x, &star[i].y, &star[i].value);

line[cnt_l].x =  star[i].x - xx;
line[cnt_l].y1 = star[i].y - yy;
line[cnt_l].y2 = star[i].y + yy;
line[cnt_l].value = star[i].value;
line[cnt_l].end = false;
cnt_l++;

line[cnt_l].x = star[i].x + xx;
line[cnt_l].y1 = star[i].y - yy;
line[cnt_l].y2 = star[i].y + yy;
line[cnt_l].value = star[i].value;
line[cnt_l].end = true;
cnt_l++;

dy[cnt_d++] = star[i].y - yy;
dy[cnt_d++] = star[i].y + yy;
}

sort(line, line + cnt_l, cmp_2);
sort(dy, dy + cnt_d, cmp_1);
cnt_d = (int)(unique(dy, dy + cnt_d) - dy);

build_tree(0, 0, cnt_d - 1);

for (int i = 0; i < cnt_d; i++)
{
mdi[dy[i]] = i;
}

ans = 0;
for (int i = 0; i < cnt_l; i++)
{
L1 = mdi[line[i].y1];
R1 = mdi[line[i].y2];

if (!line[i].end)
{
ans = max(tree[0].max_value, ans);
}
else
{
add_tree(0, L1, R1, -1 * line[i].value);
}
}

cout << ans << endl;
}

return 0;
}```

100 篇文章37 人订阅

0 条评论

## 相关文章

2427

971

5659

49611

### DIGITS 2支持多GPU自动扩展 实现深度学习性能倍增

DIGITS 是一款面向数据科学家和研究人员的交互式深度学习开发工具，设计的初衷是为了适应优越的深度神经网络的迅速开发和部署。NVIDIA在2015年3月份推出...

20910

### 基于深度学习的文本生成【附217页PPT下载】

【导读】文本生成是许多NLP应用程序的关键组件。在数据驱动方法中，它用语言表达知识库的内容或从丰富的语言产生自然英语句子表示，例如依赖树或抽象含义表示。另一方面...

2085

4266

2085

5725

26110