#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define debug(x) cout << #x << "= " << x << ", "
#define ll long long
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define SZ(x) (int) x.size()
#define wall cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define int long long
const int maxn = 4e5 + 10 , inf = 1e18;
int n , l[maxn] , r[maxn] , hole[maxn] , cost[maxn] , m , tree[2][maxn << 2];
void Build(int ty , int node = 1 , int nl = 0 , int nr = n)
{
if(nr - nl == 1)
{
if(ty == 0 && nl == 0) tree[ty][node] = 0;
else if(ty == 1 && nr == n) tree[ty][node] = 0;
else tree[ty][node] = inf;
return;
}
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
Build(ty , lc , nl , mid); Build(ty , rc , mid , nr);
tree[ty][node] = min(tree[ty][lc] , tree[ty][rc]);
}
void update(int ty , int ind , int val , int node = 1 , int nl = 0 , int nr = n)
{
if(nr - nl == 1)
{
tree[ty][node] = min(tree[ty][node] , val);
return;
}
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(ind < mid) update(ty , ind , val , lc , nl , mid);
else update(ty , ind , val , rc , mid , nr);
tree[ty][node] = min(tree[ty][lc] , tree[ty][rc]);
}
int Get(int ty , int l , int r , int node = 1 , int nl = 0 , int nr = n)
{
if(r <= nl || nr <= l) return inf;
if(l <= nl && nr <= r) return tree[ty][node];
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
return min(Get(ty , l , r , lc , nl , mid) , Get(ty , l , r , rc , mid , nr));
}
int32_t main()
{
fast;
cin >> m >> n;
vector <int> vec;
bool flg = false;
for(int i = 0 ; i < m ; i++)
{
cin >> l[i] >> r[i] >> hole[i] >> cost[i];
if(l[i] == 1) flg = true;
vec.pb(l[i]); vec.pb(r[i]); vec.pb(hole[i]); vec.pb(min(n , r[i] + 1));
}
if(n == 1)
{
cout << 0 << endl;
return 0;
}
if(!flg)
{
cout << -1 << endl;
return 0;
}
sort(vec.begin() , vec.end());
vec.resize(unique(vec.begin() , vec.end()) - vec.begin());
n = SZ(vec);
for(int i = 0 ; i < m ; i++)
{
l[i] = lower_bound(vec.begin() , vec.end() , l[i]) - vec.begin();
r[i] = lower_bound(vec.begin() , vec.end() , r[i]) - vec.begin();
r[i]++;
hole[i] = lower_bound(vec.begin() , vec.end() , hole[i]) - vec.begin();
}
Build(0); Build(1);
int ans = inf;
for(int i = 0 ; i < m ; i++)
{
int r0 = Get(0 , l[i] , r[i]) , r1 = Get(1 , l[i] , r[i]);
int res = r0 + r1 + cost[i];
ans = min(ans , res);
update(0 , hole[i] , r0 + cost[i]); update(1 , hole[i] , r1 + cost[i]);
}
if(ans == inf) cout << -1 << endl;
else cout << ans << endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
336 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
336 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
3 ms |
480 KB |
Output is correct |
18 |
Correct |
2 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
2 ms |
468 KB |
Output is correct |
21 |
Correct |
1 ms |
400 KB |
Output is correct |
22 |
Correct |
2 ms |
596 KB |
Output is correct |
23 |
Correct |
2 ms |
560 KB |
Output is correct |
24 |
Correct |
2 ms |
552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
336 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
3 ms |
480 KB |
Output is correct |
18 |
Correct |
2 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
2 ms |
468 KB |
Output is correct |
21 |
Correct |
1 ms |
400 KB |
Output is correct |
22 |
Correct |
2 ms |
596 KB |
Output is correct |
23 |
Correct |
2 ms |
560 KB |
Output is correct |
24 |
Correct |
2 ms |
552 KB |
Output is correct |
25 |
Correct |
18 ms |
2388 KB |
Output is correct |
26 |
Correct |
58 ms |
7056 KB |
Output is correct |
27 |
Correct |
193 ms |
11504 KB |
Output is correct |
28 |
Correct |
147 ms |
10644 KB |
Output is correct |
29 |
Correct |
129 ms |
9688 KB |
Output is correct |
30 |
Correct |
182 ms |
11928 KB |
Output is correct |
31 |
Correct |
252 ms |
18820 KB |
Output is correct |
32 |
Correct |
217 ms |
14648 KB |
Output is correct |
33 |
Correct |
32 ms |
6512 KB |
Output is correct |
34 |
Correct |
115 ms |
13744 KB |
Output is correct |
35 |
Correct |
167 ms |
27064 KB |
Output is correct |
36 |
Correct |
302 ms |
27052 KB |
Output is correct |
37 |
Correct |
254 ms |
26984 KB |
Output is correct |
38 |
Correct |
235 ms |
27044 KB |
Output is correct |