#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
using namespace std;
const ll INF = 1e16;
struct SegTree {
vector <ll> aint;
int n;
inline void init(int _n) {
n = _n;
aint.resize(4 * n + 1, INF);
}
void update(int nod, int left, int right, int pos, ll val) {
aint[nod] = min(aint[nod], val);
if(left < right) {
int mid = (left + right) / 2;
if(pos <= mid) update(2 * nod, left, mid, pos, val);
else update(2 * nod + 1, mid + 1, right, pos, val);
}
}
ll query(int nod, int left, int right, int l, int r) {
if(l <= left && right <= r) {
return aint[nod];
}
else {
int mid = (left + right) / 2;
ll ans = INF;
if(l <= mid) ans = min(ans, query(2 * nod, left, mid, l, r));
if(mid < r) ans = min(ans, query(2 * nod + 1, mid + 1, right, l, r));
return ans;
}
}
};
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, n, m;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> m >> n;
vector <int> l(m + 1), r(m + 1), pos(m + 1), nrm;
vector <ll> cst(m + 1);
for(i = 1; i <= m; i++) {
cin >> l[i] >> r[i] >> pos[i] >> cst[i];
nrm.push_back(l[i]);
nrm.push_back(r[i]);
nrm.push_back(pos[i]);
}
sort(nrm.begin(), nrm.end());
nrm.resize(unique(nrm.begin(), nrm.end()) - nrm.begin());
int sz = nrm.size();
map <int, int> mp;
for(i = 0; i < sz; i++) {
mp[nrm[i]] = i + 1;
}
SegTree st[3];
for(i = 1; i <= 2; i++) {
st[i].init(sz);
}
vector < vector <ll> > dp(m + 1, vector<ll>(4, INF));
for(i = 1; i <= m; i++) {
if(l[i] == 1) {
dp[i][1] = min(dp[i][1], cst[i]);
}
if(r[i] == n) {
dp[i][2] = min(dp[i][2], cst[i]);
}
if(l[i] == 1 && r[i] == n) {
dp[i][3] = min(dp[i][3], cst[i]);
}
l[i] = mp[l[i]], r[i] = mp[r[i]], pos[i] = mp[pos[i]];
dp[i][1] = min(dp[i][1], cst[i] + st[1].query(1, 1, sz, l[i], r[i]));
dp[i][2] = min(dp[i][2], cst[i] + st[2].query(1, 1, sz, l[i], r[i]));
dp[i][3] = min(dp[i][3], cst[i] + st[1].query(1, 1, sz, l[i], r[i]) + st[2].query(1, 1, sz, l[i], r[i]));
dp[i][3] = min(dp[i][3], dp[i][1] + dp[i][2] - cst[i]);
for(int j = 1; j <= 2; j++) {
st[j].update(1, 1, sz, pos[i], dp[i][j]);
}
}
ll ans = INF;
for(i = 1; i <= m; i++) {
ans = min(ans, dp[i][3]);
}
if(ans == INF) {
cout << -1;
return 0;
}
cout << ans;
//cin.close();
//cout.close();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
384 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
3 ms |
384 KB |
Output is correct |
13 |
Correct |
3 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
384 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
3 ms |
384 KB |
Output is correct |
13 |
Correct |
3 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
3 ms |
384 KB |
Output is correct |
17 |
Correct |
4 ms |
640 KB |
Output is correct |
18 |
Correct |
4 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
768 KB |
Output is correct |
20 |
Correct |
5 ms |
512 KB |
Output is correct |
21 |
Correct |
4 ms |
512 KB |
Output is correct |
22 |
Correct |
5 ms |
768 KB |
Output is correct |
23 |
Correct |
20 ms |
768 KB |
Output is correct |
24 |
Correct |
5 ms |
768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
384 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
3 ms |
384 KB |
Output is correct |
13 |
Correct |
3 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
3 ms |
384 KB |
Output is correct |
17 |
Correct |
4 ms |
640 KB |
Output is correct |
18 |
Correct |
4 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
768 KB |
Output is correct |
20 |
Correct |
5 ms |
512 KB |
Output is correct |
21 |
Correct |
4 ms |
512 KB |
Output is correct |
22 |
Correct |
5 ms |
768 KB |
Output is correct |
23 |
Correct |
20 ms |
768 KB |
Output is correct |
24 |
Correct |
5 ms |
768 KB |
Output is correct |
25 |
Correct |
32 ms |
3328 KB |
Output is correct |
26 |
Correct |
124 ms |
9976 KB |
Output is correct |
27 |
Correct |
363 ms |
21104 KB |
Output is correct |
28 |
Correct |
207 ms |
14572 KB |
Output is correct |
29 |
Correct |
300 ms |
17520 KB |
Output is correct |
30 |
Correct |
340 ms |
16504 KB |
Output is correct |
31 |
Correct |
718 ms |
32880 KB |
Output is correct |
32 |
Correct |
623 ms |
27632 KB |
Output is correct |
33 |
Correct |
78 ms |
9588 KB |
Output is correct |
34 |
Correct |
340 ms |
23968 KB |
Output is correct |
35 |
Correct |
392 ms |
47400 KB |
Output is correct |
36 |
Correct |
835 ms |
47364 KB |
Output is correct |
37 |
Correct |
606 ms |
47340 KB |
Output is correct |
38 |
Correct |
631 ms |
47488 KB |
Output is correct |