首页 > 其他分享 >P10837 『FLA - I』云音泛

P10837 『FLA - I』云音泛

时间:2024-08-05 11:49:28浏览次数:15  
标签:P10837 int ll st 云音泛 low poi FLA now

原题链接

题解

修改玫瑰 \(i\) ,对答案的影响是:

减去只有玫瑰 \(i\) 的区间,加上只有玫瑰 \(i\) 和另一个玫瑰的区间,加上 m

因此我们对每个玫瑰 \(i\) ,维护上述两个区间长度

由于每个玫瑰开花时间一样,所以我们可以用扫描线的思想,对所有区间的端点离散化排序,然后升序遍历,由于开花时间一样,所以我们可以用队列维护当前区间(当前端点到下一端点)的玫瑰

只有一朵玫瑰,或者两朵玫瑰时维护上述值

code

#include<bits/stdc++.h>
using namespace std;

#define int long long
/*
#define lb long double
#define lowbit(x) ((x)&(-x))
const ll inf=1e18;
const ll mod=1e9+7;

const ll N=4e5;
ll qpow(ll a,ll n)
{
    ll res=1;
    while(n)
    {
        if(n&1) res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}
ll inv(ll x)
{
    return qpow(x,mod-2);
}
ll fa[2000005];
ll finds(ll now){return now==fa[now]?now:finds(fa[now]);}

vector<ll> G[200005];

ll dfn[200005],low[200005];
ll cnt=0,num=0;
ll in_st[200005]={0};
stack<ll> st;
ll belong[200005]={0};

void scc(ll now,ll fa)
{
    dfn[now]=++cnt;
    low[now]=dfn[now];
    in_st[now]=1;
    st.push(now);

    for(auto next:G[now])
    {
        if(next==fa) continue;

        if(!dfn[next])
        {
            scc(next,now);
            low[now]=min(low[now],low[next]);
        }
        else if(in_st[next])
        {
            low[now]=min(low[now],dfn[next]);
        }
    }

    if(low[now]==dfn[now])
    {
        ll x;
        num++;
        do
        {
            x=st.top();
            st.pop();
            in_st[x]=0;
            belong[x]=num;
        }while(x!=now);
    }
}
*/


int poi[400005];
int sum[200005][3]={0};
int t[200005];

void solve()
{
    int n,m;
    cin>>n>>m;

    int tot=0;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        cin>>t[i];
        poi[++cnt]=t[i];
        poi[++cnt]=t[i]+m;
    }

    sort(t+1,t+1+n);
    sort(poi+1,poi+1+cnt);

    int len=unique(poi+1,poi+1+cnt)-poi-1;

    queue<int> q;
    int it=1;
    for(int i=1;i<=len;i++)
    {
        while(q.size()&&t[q.front()]+m<=poi[i]) q.pop();
        while(it<=n&&t[it]==poi[i]) q.push(it++);
        //printf("i:%d poi:%d it:%d\n",i,poi[i],it);
        if(q.size()==1)
        {
            sum[q.front()][1]+=poi[i+1]-poi[i];
            tot+=poi[i+1]-poi[i];
        }
        if(q.size()==2)
        {
            sum[q.front()][2]+=poi[i+1]-poi[i];
            sum[q.back()][2]+=poi[i+1]-poi[i];
        }
    }

    int ans=0;
    for(int i=1;i<=n;i++)
    {
        //printf("i:%d  sum1:%d  sum2:%d\n",i,sum[i][1],sum[i][2]);
        ans=max(ans,tot-sum[i][1]+sum[i][2]+m);
    }

    cout<<ans<<'\n';
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TT=1;
    //cin>>TT;
    while(TT--) solve();
    return 0;
}



标签:P10837,int,ll,st,云音泛,low,poi,FLA,now
From: https://www.cnblogs.com/pure4knowledge/p/18342946

相关文章

  • Flask 应用程序的 POST 请求出现 405 method not allowed 错误
    我有一个简单的Web应用程序,可以使用以下代码向选定的受访者发送消息(使用TwilioAPI):app.pyclient=Client(account_sid,auth_token)@app.route('/')defindex():returnrender_template('index.html')@app.route('/send_sms',methods=['POST......
  • FLASK 相关链接
    FLASK中文文档:https://dormousehole.readthedocs.io/en/latest/FLASK教程:https://www.bookstack.cn/read/head-first-flask/README.mdhttp://www.coolpython.net/flask_tutorial/basic/route.htmlhttp://www.pythondoc.com/flask-mega-tutorial/index.htmlPython中文学......
  • python+flask计算机毕业设计健康管理系统的设计与实现(程序+开题+论文)
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景近年来,随着人们生活水平的提高和健康意识的增强,健康管理已成为社会关注的焦点。传统的健康管理方式往往依赖于纸质记录和医生的口头建议,这......
  • python+flask计算机毕业设计实验室信息化管理系统(程序+开题+论文)
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景在当今快速发展的科技时代,实验室作为科研与教学的核心场所,其管理效率和信息化水平直接影响到研究成果的质量和速度。传统的实验室管理方式......
  • python+flask计算机毕业设计中国诗词鉴赏网站(程序+开题+论文)
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景中国诗词作为中华文化的重要组成部分,承载着千年的历史与文化底蕴。从古至今,诗词一直是文人墨客表达情感、描绘景象的重要工具。然而,随着时......
  • python+flask计算机毕业设计装修公司管理系统(程序+开题+论文)
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景近年来,随着城市化进程的加速和人们生活水平的提高,装修行业迎来了前所未有的发展机遇。然而,传统装修公司管理方式存在诸多弊端,如信息不透明......
  • 从数据爬取到可视化展示:Flask框架与ECharts深度解析
    目录......
  • 001在vscode中创建flask项目框架
    目录在vscode中创建flask项目1.配置flask环境2.导入以及创建flask框架在vscode中创建flask项目1.配置flask环境先配置解释器然后再该虚拟环境下进行安装flask模块进行该指令:pipinstallflask==版本号2.导入以及创建flask框架在桌面或者文件中建立一个文件夹将其移......
  • 002.flask的基本使用
    目录flask的基本使用1.基本使用2.传参的两种方式3.通过返回html网页来展示4.通过面向对象传参给html网页5.在html里面写条件语句6.在html中用循环7.总结flask的基本使用1.基本使用点三角形运行复制http://127.0.0.1:5000到浏览器上软后加上面的/index得到如下:可以给其添......
  • Flask 快速搭建模板1
    快速搭建基础框架成品预览pip安装需要导入的基础包pipinstallflaskpipinstallflask-sqlalchemypipinstallflask-wtfpipinstallbootstrap-flaskpipinstallflask-loginpipinstallflask-moment创建目录结构typenul>main.pytypenul>config.pytyp......