#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 100'010;
const int M = 300'010;
const ll inf = 1e15;
int n, m;
int a[N], b[N], c[N];
ll d[N];
struct seg {
ll t[2*M];
ll get(int l, int r)
{
l += M; r += M;
ll ans = inf;
while (l < r) {
if (l&1) ans = min(ans, t[l++]);
if (r&1) ans = min(ans, t[--r]);
l /= 2; r /= 2;
}
return ans;
}
void up(int i, ll x)
{
i += M;
while (i) {
t[i] = min(t[i], x);
i /= 2;
}
}
} dpr, dpl;
vector<pair<int,int*>> cmp_vec;
int compress()
{
vector<int> vec;
for (auto [x, _] : cmp_vec)
vec.push_back(x);
sort(vec.begin(), vec.end());
vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
for (auto [x, p] : cmp_vec) {
if (p) {
*p = lower_bound(vec.begin(), vec.end(), x)
- vec.begin();
}
}
return vec.size();
}
void init_dp()
{
fill(dpr.t, dpr.t + 2*M, inf);
fill(dpl.t, dpl.t + 2*M, inf);
dpr.up(m-1, 0);
dpl.up(0, 0);
}
ll calc_ans()
{
init_dp();
ll ans = inf;
Loop (dev,0,n) {
ans = min( dpl.get(a[dev], b[dev]+1)
+ dpr.get(a[dev], b[dev]+1)
+ d[dev],
ans);
ll mnr = dpr.get(c[dev], b[dev]+1);
ll mnl = dpl.get(a[dev], c[dev]+1);
dpr.up(c[dev], mnr + d[dev]);
dpl.up(c[dev], mnl + d[dev]);
}
return ans;
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n >> m;
Loop (i,0,n) {
cin >> a[i] >> b[i] >> c[i] >> d[i];
cmp_vec.push_back({a[i], &a[i]});
cmp_vec.push_back({b[i], &b[i]});
cmp_vec.push_back({c[i], &c[i]});
}
cmp_vec.push_back({1, NULL});
cmp_vec.push_back({m, NULL});
m = compress();
ll ans = calc_ans();
cout << (ans == inf? -1: ans) << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
4 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Correct |
4 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
4 ms |
9684 KB |
Output is correct |
7 |
Correct |
4 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
4 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Correct |
4 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
4 ms |
9684 KB |
Output is correct |
7 |
Correct |
4 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
5 ms |
9684 KB |
Output is correct |
10 |
Correct |
4 ms |
9684 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
5 ms |
9700 KB |
Output is correct |
13 |
Correct |
6 ms |
9684 KB |
Output is correct |
14 |
Correct |
4 ms |
9676 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
4 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Correct |
4 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
4 ms |
9684 KB |
Output is correct |
7 |
Correct |
4 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
5 ms |
9684 KB |
Output is correct |
10 |
Correct |
4 ms |
9684 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
5 ms |
9700 KB |
Output is correct |
13 |
Correct |
6 ms |
9684 KB |
Output is correct |
14 |
Correct |
4 ms |
9676 KB |
Output is correct |
15 |
Correct |
5 ms |
9684 KB |
Output is correct |
16 |
Correct |
5 ms |
9680 KB |
Output is correct |
17 |
Correct |
7 ms |
9812 KB |
Output is correct |
18 |
Correct |
5 ms |
9812 KB |
Output is correct |
19 |
Correct |
7 ms |
9812 KB |
Output is correct |
20 |
Correct |
5 ms |
9812 KB |
Output is correct |
21 |
Correct |
5 ms |
9820 KB |
Output is correct |
22 |
Correct |
6 ms |
9812 KB |
Output is correct |
23 |
Correct |
6 ms |
9808 KB |
Output is correct |
24 |
Correct |
6 ms |
9808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
4 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Correct |
4 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
4 ms |
9684 KB |
Output is correct |
7 |
Correct |
4 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
5 ms |
9684 KB |
Output is correct |
10 |
Correct |
4 ms |
9684 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
5 ms |
9700 KB |
Output is correct |
13 |
Correct |
6 ms |
9684 KB |
Output is correct |
14 |
Correct |
4 ms |
9676 KB |
Output is correct |
15 |
Correct |
5 ms |
9684 KB |
Output is correct |
16 |
Correct |
5 ms |
9680 KB |
Output is correct |
17 |
Correct |
7 ms |
9812 KB |
Output is correct |
18 |
Correct |
5 ms |
9812 KB |
Output is correct |
19 |
Correct |
7 ms |
9812 KB |
Output is correct |
20 |
Correct |
5 ms |
9812 KB |
Output is correct |
21 |
Correct |
5 ms |
9820 KB |
Output is correct |
22 |
Correct |
6 ms |
9812 KB |
Output is correct |
23 |
Correct |
6 ms |
9808 KB |
Output is correct |
24 |
Correct |
6 ms |
9808 KB |
Output is correct |
25 |
Correct |
24 ms |
10836 KB |
Output is correct |
26 |
Correct |
42 ms |
13060 KB |
Output is correct |
27 |
Correct |
115 ms |
18708 KB |
Output is correct |
28 |
Correct |
115 ms |
23356 KB |
Output is correct |
29 |
Correct |
88 ms |
16584 KB |
Output is correct |
30 |
Correct |
151 ms |
23492 KB |
Output is correct |
31 |
Correct |
173 ms |
23432 KB |
Output is correct |
32 |
Correct |
200 ms |
23492 KB |
Output is correct |
33 |
Correct |
21 ms |
12240 KB |
Output is correct |
34 |
Correct |
90 ms |
16600 KB |
Output is correct |
35 |
Correct |
93 ms |
23476 KB |
Output is correct |
36 |
Correct |
200 ms |
23432 KB |
Output is correct |
37 |
Correct |
141 ms |
23388 KB |
Output is correct |
38 |
Correct |
128 ms |
23416 KB |
Output is correct |