【JOISC 2020 Day4】治疗计划
题目
题目译自 JOISC 2020 Day4 T3「治療計画 / Treatment Project」
JOI 国有 个房屋，并从 到 编号。这些房屋沿一条直线升序排列。每个房屋有一个居民住在里面。住在编号为 的房屋里的居民用居民 表示。
最近，新冠病毒出现了，并且所有居民都被感染了。为了解决这个问题，有 个治疗方案被提出。第 个治疗方案的花费为 。如果执行计划 ，则会发生以下事件：
在第 天的晚上，如果居民 满足 ，且他感染了新冠病毒，那么他就会被治愈。
病毒按如下方式传染相邻的居民：
如果在某天的早晨，居民 被病毒感染，那么在同一天的中午，居民 （如果 ）和居民 （如果 ）就会被感染。
一个已经被治愈的居民可以再次被病毒感染。
你是 JOI 国的首相，你需要选取某些方案，使得满足以下条件：
条件：在所有被选中的方案全部执行后，没有居民感染病毒。
在某一天可以执行多个计划。
写一个程序，给定房屋和治疗计划的信息，求出能否满足以上条件，若满足，求出最小可能花费。
输入格式
从标准输入中读取以下内容：
第一行两个整数 ；
接下来 行，每行四个整数 ，表示一个治疗方案。
输出格式
输出一行到标准输出。如果条件无法满足，则输出 ，否则输出最小总花费。
样例
样例输入 1
10 5
2 5 10 3
1 1 6 5
5 2 8 3
7 6 10 4
4 1 3 1
样例输出 1
7
样例说明 1
在样例 中，你可以按照如下方式执行计划：
在第二天的晚上，执行计划 ，之后居民 被治愈了，现在只有居民 被病毒感染；
在第三天的中午，居民 被病毒感染。现在居民 被病毒感染；
在第四天的中午，居民 被病毒感染。现在居民 被病毒感染；
在第四天的晚上，执行计划 ，之后居民 被治愈了，现在只有居民 被病毒感染；
在第五天的中午，居民 被病毒感染。现在居民 被病毒感染；
在第五天的晚上，执行计划 ，之后居民 被治愈了，现在没有居民被感染了。
执行计划 的总花费为 。并且没有比这个花费更少且满足条件的方案，所以输出 。
样例输入 2
10 5
2 6 10 3
1 1 5 5
5 2 7 3
8 6 10 4
4 1 3 1
样例输出 2
-1
样例说明 2
因为无法满足条件，所以输出 。
样例输入 3
10 5
1 5 10 4
1 1 6 5
1 4 8 3
1 6 10 3
1 1 3 1
样例输出 3
7
样例说明 3
这组样例满足子任务 1 的限制。
数据范围与提示
对于所有数据，满足 ，保证：
详细子任务及附加限制如下表所示：
子任务编号 附加限制 分值
无附加限制
思路
首先考虑一个简单的 n2 dp，令 fi 表示在 ti 天， 1 到 ri 的所有人都已经被治疗完毕了的最小花费。
然后考虑 Dijkstra 一样的方式进行 dp，每次找到所有尚未松弛的 i 中 fi 最小的那个进行转移，可以从 i 向 j 转移的条件是 ri−lj+1≥|ti−tj|（非常容易理解）.
最后只需找到满足 ri=n 的所有 fi 的最小值即可。
可以注意到，每个点只会被松弛一次。
由此，用线段树维护尚未松弛的点，并用堆维护已经松弛的点即可快速模拟该过程。
代码
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N=1e5+77;
int n,m,ql,qr,qw;
bool vis[N];
struct pj
{
int t,l,r,c,w;
}p[N];
bool cmpt(pj A,pj B){return A.t<B.t; }
typedef pair<ll,int>pli;
pli now;
priority_queue<pli,vector<pli>,greater<pli> >Q;
typedef pair<int,int>pii;
pii qx;
struct tree
{
#define ls x*2
#define rs x*2+1
vector<pii>t[N*4];
void ins(int x,int L,int R)
{
t[x].push_back(qx);
if(L==R)return;
int mid=(L+R)/2;
if(ql<=mid)ins(ls,L,mid);
else ins(rs,mid+1,R);
}
void query(int x,int L,int R)
{
if(!t[x].size())return;
if(ql<=L&&R<=qr)
{
pii i;
for(i=t[x].back(); t[x].size()&&qw>=i.fi; i=t[x].back())
{
t[x].pop_back();
if(!vis[i.se])
{
vis[i.se]=1;
Q.push(pli(now.fi+p[i.se].c,i.se));
}
}
return;
}int mid=(L+R)/2;
if(ql<=mid)query(ls,L,mid);
if(qr>mid)query(rs,mid+1,R);
}
}T1,T2;
int P[N];
bool cmpw(int x,int y){return p[x].w>p[y].w; }
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
P[i]=i;
scanf("%d%d%d%d",&p[i].t,&p[i].l,&p[i].r,&p[i].c);
p[i].w=p[i].l-p[i].t;
}
sort(p+1,p+m+1,cmpt);
sort(P+1,P+m+1,cmpw);
for(int i=1; i<=m; i++)
{
ql=P[i];
qx.fi=p[ql].w;
qx.se=ql;
T1.ins(1,1,m);
p[ql].w=p[ql].l+p[ql].t;
}
sort(P+1,P+m+1,cmpw);
for(int i=1; i<=m; i++)
{
ql=P[i];
qx.fi=p[ql].w;
qx.se=ql;
T2.ins(1,1,m);
if(p[ql].l==1)
Q.push(pli(p[ql].c,ql));
}
int i;
while(!Q.empty())
{
now=Q.top(); Q.pop(); i=now.se;
if(p[i].r==n)
{
printf("%lld",now.fi);
return 0;
}
ql=1; qr=i-1; qw=p[i].r-p[i].t+1;
if(ql<=qr)T1.query(1,1,m);
ql=i+1; qr=m; qw=p[i].r+p[i].t+1;
if(ql<=qr)T2.query(1,1,m);
}
puts("-1");
return 0;
}