20 RE求助
查看原帖
20 RE求助
823773
_sh1kong_楼主2023/7/16 14:58

RT

#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
#define LL long long
#define ls(k) k << 1
#define rs(k) k << 1 | 1

const int N = 3e5 + 5, M = 1e5 + 3;

using namespace std;

int n, l, r;

int ls[N >> 4], rs[N >> 4], mn[N >> 4];

int f[N];

//f[x] 
//l ~ x 最小花费 

struct node

{
	int a, b, cost;
}cow[N];

bool cmp(node a, node b)

{
	return a.b < b.b;
}

void pushup(int k)

{
	mn[k] = min(mn[ls(k)], mn[rs(k)]);
}

void build(int k, int l, int r)

{
	ls[k] = l, rs[k] = r;
	if (l == r)
	{
		mn[k] = f[l];
		return ;
	}
	int mid = (l + r) >> 1;
	build(ls(k), l, mid), build(rs(k), mid + 1, r);
	pushup(k);
}

void modify(int k, int pos, int v)

{
	int l = ls[k], r = rs[k];
	if (l == r)
	{
		mn[k] = v;
		return ;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) modify(ls(k), pos, v);
	else modify(rs(k), pos, v);
	pushup(k);
}

int query(int k, int L, int R)

{
	int l = ls[k], r = rs[k];
	if (L <= l && r <= R) return mn[k];
	int mid = (l + r) >> 1, ans = 1 << 30;
	if (L <= mid) ans = min(ans, query(ls(k), L, R));
	if (R > mid) ans = min(ans, query(rs(k), L, R));
	return ans;
}
	
signed main()

{
	IOS;
	
	cin >> n >> l >> r;
	for (int i = 1; i <= n; i ++ ) cin >> cow[i].a >> cow[i].b >> cow[i].cost;
	sort(cow + 1, cow + n + 1, cmp);
	memset(f, 0x3f, sizeof f);
	f[l] = 0;
	build(1, l, r);
	for (int i = 1; i <= n; i ++ )
	{
		f[cow[i].b] = min(f[cow[i].b], query(1, cow[i].a - 1, cow[i].b) + cow[i].cost);
		modify(1, cow[i].b, f[cow[i].b]);
		if (cow[i].b >= r)
		{
			if (f[cow[i].b] == 0x3f3f3f3f) cout << "-1";
			else cout << f[cow[i].b];
			return 0;
		}
	}
}
2023/7/16 14:58
加载中...