51Nod-1208-Stars in Your Window

ACM模版

描述

题解

线段树 + 扫描线。

把星星转化为矩形,把矩形转化成线段,然后求哪一条线段权值最大。具体的思路可以看看 光速小子0511’s blog,太强啦~~~

代码

#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)
    {
        add_tree(lson, L, R, c);
    }
    else if (L >= m + 1)
    {
        add_tree(rson, L, R, c);
    }
    else
    {
        add_tree(lson, L, m, c);
        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)
            {
                add_tree(0, L1, R1, line[i].value);
                ans = max(tree[0].max_value, ans);
            }
            else
            {
                add_tree(0, L1, R1, -1 * line[i].value);
            }
        }

        cout << ans << endl;
    }

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ArrayZoneYour的专栏

周期序预测列问题中的朴素模型——周期跟随模型(Seasonal Persistence)

在处理时间序列问题时,人们通常使用跟随算法(将前一个时间单位的观测值作为当前时间的预测值)预测的结果作为预测性能的基准。

2427
来自专栏新智元

旧照片着色修复神器!自注意力GAN效果惊艳

图像着色、图像增强、恢复旧图像等是计算机视觉领域的热点问题,不过,用一个模型很好地实现多个任务的研究不多。

971
来自专栏量子位

深度学习动手入门:GitHub上四个超棒的TensorFlow开源项目

问耕 编译自 Source Dexter 量子位 出品 | 公众号 QbitAI 作者简介:akshay pai,数据科学工程师,热爱研究机器学习问题。Sour...

5659
来自专栏机器之心

资源 | 谷歌全attention机器翻译模型Transformer的TensorFlow实现

选自GitHub 机器之心编译 参与:黄小天、Smith 谷歌前不久在 arXiv 上发表论文《Attention Is All You Need》,提出一种完...

49611
来自专栏CSDN技术头条

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

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

20910
来自专栏专知

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

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

2085
来自专栏Python小屋

Python+numpy实现矩阵QR分解

感谢广东东软学院计算机系赵晨杰老师的交流。 如果实(复)非奇异矩阵A能够化成正交(酉)矩阵Q与实(复)非奇异上三角矩阵R的乘积,即A=QR,则称其为A的QR分解...

4266
来自专栏新智元

MXNet 作者李沐:用深度学习做图像分类,教程+代码

2085
来自专栏吉浦迅科技

如何在Jetson TX2上用Python捕获摄像头影像,并用Caffe进行推理

本文转载自JK Jung的帖子:https://jkjung-avt.github.io/tx2-camera-caffe/ 如果有侵犯到贴主利益,请立刻跟我联...

5725
来自专栏CDA数据分析师

AI可能真的要代替插画师了……

事先声明,这篇文章的标题绝不是在耸人听闻。事情的起因是今天早上在朋友圈看到同学在转发一篇论文,名字叫《Create Anime Characters with ...

26110

扫码关注云+社区

领取腾讯云代金券