RE 了,求调啊
查看原帖
RE 了,求调啊
1411354
xf20280111楼主2025/7/22 19:43
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e4 + 10;
const int M = 86399 + 10;

int n,m,e;
struct node{
	int l,r,s;
}a[M * 4];
bool cmp(node ljw,node wjl){
	return ljw.r < wjl.r;
}

int dp[M];
struct tree{
	int minn;
}t[N * 4];

void build(int l,int r,int p){
	if (l == r) {t[p].minn = 0x3f3f3f3f;return;}
	int mid = (l + r) / 2;
	build(l,mid,(p << 1));
	build(mid + 1,r,(p << 1) + 1);
	t[p].minn = min(t[(p << 1)].minn,t[(p << 1) + 1].minn);
}
void change(int l,int r,int p,int x,int v){
	if (l == r){t[p].minn = v;return;}
	int mid = (l + r) / 2;
	if (x <= mid) change(l,mid,(p << 1),x,v);
	else change(mid + 1,r,(p << 1) + 1,x,v);
	t[p].minn = min(t[(p << 1)].minn,t[(p << 1) + 1].minn);
}
int ask(int l,int r,int p,int ql,int qr){
	if (ql <= l and r <= qr) return t[p].minn;
	int mid = (l + r) / 2;
	if (qr <= mid) return ask(l,mid,(p << 1),ql,qr);
	if (ql > mid) return ask(mid + 1,r,(p << 1) + 1,ql,qr);
	return min(ask(l,mid,(p << 1),ql,qr),ask(mid + 1,r,(p << 1) + 1,ql,qr));
}
int main(){
	cin >> n >> m >> e; 
	for (int i = 1;i <= n;i++){
		cin >> a[i].l >> a[i].r >> a[i].s;
		a[i].l = max(m,a[i].l);
		a[i].r = min(e,a[i].r);
	}
	
	build(m - 1,e,1);
	change(m - 1,e,1,m - 1,0); 
	sort(a + 1,a + n + 1,cmp);
	memset(dp,0x3f3f3f3f,sizeof(dp));
	dp[m - 1] = 0;
	for (int i = 1;i <= n;i++){
		if (a[i].l > a[i].r) continue;
		dp[a[i].r] = min(dp[a[i].r],ask(m - 1,e,1,a[i].l - 1,a[i].r) + a[i].s);
		change(m - 1,e,1,a[i].r,dp[a[i].r]);
	}
	if (dp[e] >= 0x3f3f3f3f) cout << -1;
	else cout << dp[e];
	return 0;
}
2025/7/22 19:43
加载中...