Submission #8371669


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
#define def infl
template<class V, int NV> struct SegTree { //[l,r)
	V comp(V& l, V& r) { return min(l, r); };

	vector<V> val; SegTree() { val = vector<V>(NV * 2, def); }
	V get(int x, int y, int l = 0, int r = NV, int k = 1) {
		if (r <= x || y <= l)return def; if (x <= l && r <= y)return val[k];
		auto a = get(x, y, l, (l + r) / 2, k * 2);
		auto b = get(x, y, (l + r) / 2, r, k * 2 + 1);
		return comp(a, b);
	}
	void update(int i, V v) {
		i += NV; val[i] = v;
		while (i > 1) i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]);
	}
	void add(int i, V v) { update(i, val[i + NV] + v); }
	V operator[](int x) { return get(x, x + 1); }
};
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     @hamayanhamayan
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/











int N, M;
vector<pair<int, int>> Q[101010];
SegTree<ll, 1 << 17> st;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M;
	rep(i, 0, M) {
		int l, r, c; cin >> l >> r >> c;
		Q[r].push_back({ l, c });
	}

	st.update(1, 0);
	rep(r, 1, N + 1) {
		fore(p, Q[r]) {
			int l = p.first;
			int c = p.second;
			st.update(r, min(st[r], st.get(l, r) + c));
		}
	}
	ll ans = st[N];
	if (ans == infl) ans = -1;
	cout << ans << endl;
}




Submission Info

Submission Time
Task D - Shortest Path on a Line
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 600
Code Size 2467 Byte
Status
Exec Time 73 ms
Memory 7680 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
× 3
× 40
Set Name Test Cases
Sample sample01.txt, sample02.txt, sample03.txt
All sample01.txt, sample02.txt, sample03.txt, in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, sample01.txt, sample02.txt, sample03.txt
Case Name Status Exec Time Memory
in01.txt 4 ms 4736 KB
in02.txt 4 ms 4736 KB
in03.txt 4 ms 4736 KB
in04.txt 4 ms 4736 KB
in05.txt 4 ms 4736 KB
in06.txt 4 ms 4736 KB
in07.txt 69 ms 6400 KB
in08.txt 64 ms 6272 KB
in09.txt 69 ms 6528 KB
in10.txt 69 ms 6528 KB
in11.txt 65 ms 6144 KB
in12.txt 69 ms 6272 KB
in13.txt 73 ms 6272 KB
in14.txt 72 ms 6400 KB
in15.txt 69 ms 6528 KB
in16.txt 71 ms 6528 KB
in17.txt 71 ms 6528 KB
in18.txt 72 ms 6528 KB
in19.txt 56 ms 6400 KB
in20.txt 56 ms 6400 KB
in21.txt 59 ms 6400 KB
in22.txt 57 ms 6400 KB
in23.txt 59 ms 6400 KB
in24.txt 60 ms 6400 KB
in25.txt 59 ms 6400 KB
in26.txt 60 ms 6656 KB
in27.txt 61 ms 7680 KB
in28.txt 60 ms 7040 KB
in29.txt 61 ms 6656 KB
in30.txt 57 ms 7040 KB
in31.txt 56 ms 7680 KB
in32.txt 54 ms 7552 KB
in33.txt 60 ms 6528 KB
in34.txt 3 ms 4736 KB
sample01.txt 3 ms 4736 KB
sample02.txt 3 ms 4736 KB
sample03.txt 3 ms 4736 KB