治疗计划[JOISC 2020 Day4]

发表于 分类于

题目链接

链接

题解

看起来似乎无从下手，那么就考虑一个类似DP的东东吧。

设 $d_i$ 表示 $[1,r_i]$ 中所有人都没有被感染的最小花费。

那么 $d_i$ 能对 $d_j$ 产生贡献当且仅当 $r_i-l_j+1\geq |T_i-T_j|$。

满足条件的 $i,j$ 连一条边，剩下的是一个形如最短路的形式。

因此如果可以优化这个建图，问题就不大了。

绝对值比较恶心，那么先按 $T_i$ 从小到大排好序。

然后枚举 $i$，根据限制在线段树上套个set优化连边就好了。

时间复杂度 $O(n\log^2n)$。

程序

为什么我比别人慢这么多QwQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
const int N=100010;
const ll inf=4e18;
struct query{
	int t,l,r,v;
	friend inline bool operator<(const query &A,const query &B) {return A.t<B.t;}
}p[N];
struct node{
	int u; ll dis;
	friend inline bool operator<(const node &A,const node &B) {return A.dis>B.dis;}
};
priority_queue<node> q;
ll dis[N];
bool vis[N];
#define lc (u<<1)
#define rc (u<<1|1)
#define ls lc,l,mid
#define rs rc,mid+1,r
struct Tnode{
	int i,val;
	friend inline bool operator<(const Tnode &A,const Tnode &B)
	{
		if(A.val!=B.val) return A.val<B.val;
		return A.i<B.i;
	}
};
struct SGT{
	set<Tnode> s[N<<2];
	void add(int u,int l,int r,int p,int v)
	{
		s[u].insert((Tnode){p,v});
		if(l==r) return;
		int mid=l+r>>1;
		p<=mid?add(ls,p,v):add(rs,p,v);
	}
	void ask(int u,int l,int r,int L,int R,int v,int i)
	{
		if(L>R) return;
		if(L<=l&&r<=R)
		{
			for(int w;s[u].size()&&(*s[u].begin()).val<=v;s[u].erase(s[u].begin()))
			{
				w=s[u].begin()->i;
				if(dis[w]>dis[i]+p[w].v)
				{
					dis[w]=dis[i]+p[w].v;
					q.push((node){w,dis[w]});
				}
			}
			return;
		}
		int mid=l+r>>1;
		if(L<=mid) ask(ls,L,R,v,i);
		if(mid<R)  ask(rs,L,R,v,i);
	}
};
SGT t[2];
int n,m;
inline ll dijkstra()
{
	fo(i,1,n)
		if(p[i].l==1) q.push((node){i,p[i].v}),dis[i]=p[i].v; 
		else dis[i]=inf;
	for(int u;!q.empty();)
	{
		u=q.top().u; q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		t[0].ask(1,1,n,1,u-1,p[u].r-p[u].t+1,u);
		t[1].ask(1,1,n,u+1,n,p[u].r+p[u].t+1,u);
	}
	ll ans=inf;
	fo(i,1,n) if(p[i].r==m) ans=min(ans,dis[i]);
	if(ans==inf) return -1;
	return ans;
}
int main()
{
	m=read(); n=read();
	fo(i,1,n) p[i].t=read(),p[i].l=read(),p[i].r=read(),p[i].v=read();
	sort(p+1,p+n+1);
	fo(i,1,n)
		t[0].add(1,1,n,i,p[i].l-p[i].t),
		t[1].add(1,1,n,i,p[i].l+p[i].t);
	printf("%lld",dijkstra());
	return 0;
}