#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, a[N], b[N], c[N];
long long d[N], t1[N*4], t2[N*4], ans = 1e18;
vector<int> coord;
void update( long long t[], int x, long long va, int l = 1, int r = coord.size(), int idx = 1 ) {
if( l == r ) return void( t[idx] = min( t[idx], va ) );
int mid = l + r >> 1;
if( x <= mid ) update( t, x, va, l, mid, idx<<1 );
else update( t, x, va, mid+1, r, idx<<1|1 );
t[idx] = min( t[idx<<1], t[idx<<1|1] );
}
long long query( long long t[], int ll, int rr, int l = 1, int r = coord.size(), int idx = 1 ) {
//printf("%d %d L : %d R : %d %lld\n",ll,rr,l,r,t[idx]);
if( l > rr || r < ll ) return 1e18;
if( l >= ll && r <= rr ) return t[idx];
int mid = l + r >> 1;
return min( query( t, ll, rr, l, mid, idx<<1 ), query( t, ll, rr, mid+1, r, idx<<1|1 ) );
}
int get( int x ) { return lower_bound( coord.begin(), coord.end(), x ) - coord.begin() + 1; }
int main()
{
fill( t1, t1 + N*4, 1e18 ), fill( t2, t2 + N*4, 1e18 );
scanf("%d %d",&m,&n);
coord.emplace_back( 1 ), coord.emplace_back( n );
for( int i = 1 ; i <= m ; i++ ) {
scanf("%d %d %d %lld",&a[i],&b[i],&c[i],&d[i]);
coord.emplace_back( a[i] ), coord.emplace_back( b[i] ), coord.emplace_back( c[i] );
}
sort( coord.begin(), coord.end() );
coord.resize( unique( coord.begin(), coord.end() ) - coord.begin() );
/*for( int i : coord ) printf("%d ",i);
printf("\n");*/
update( t1, 1, 0 ), update( t2, coord.size(), 0 );
for( int i = 1 ; i <= m ; i++ ) {
int l = get( a[i] ), r = get( b[i] ), x = get( c[i] );
//printf("%d %d %d\n",l,r,x);
long long pre = query( t1, l, r ), suf = query( t2, l, r );
ans = min( ans, pre + suf + d[i] );
//printf("%lld %lld\n",pre,suf);
update( t1, x, pre + d[i] ), update( t2, x, suf + d[i] );
}
if( ans == 1e18 ) printf("-1\n");
else printf("%lld\n",ans);
return 0;
}
Compilation message
pinball.cpp: In function 'void update(long long int*, int, long long int, int, int, int)':
pinball.cpp:12:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
pinball.cpp: In function 'long long int query(long long int*, int, int, int, int, int)':
pinball.cpp:22:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
pinball.cpp: In function 'int main()':
pinball.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&m,&n);
~~~~~^~~~~~~~~~~~~~~
pinball.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %lld",&a[i],&b[i],&c[i],&d[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 2 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 4 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 5 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 6 |
Correct |
8 ms |
6528 KB |
Output is correct |
| 7 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 8 |
Correct |
7 ms |
6656 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 2 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 4 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 5 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 6 |
Correct |
8 ms |
6528 KB |
Output is correct |
| 7 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 8 |
Correct |
7 ms |
6656 KB |
Output is correct |
| 9 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 10 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 11 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 12 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 13 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 14 |
Correct |
8 ms |
6656 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 2 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 4 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 5 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 6 |
Correct |
8 ms |
6528 KB |
Output is correct |
| 7 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 8 |
Correct |
7 ms |
6656 KB |
Output is correct |
| 9 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 10 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 11 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 12 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 13 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 14 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 15 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 16 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 17 |
Correct |
9 ms |
6656 KB |
Output is correct |
| 18 |
Correct |
9 ms |
6656 KB |
Output is correct |
| 19 |
Correct |
10 ms |
6656 KB |
Output is correct |
| 20 |
Correct |
9 ms |
6656 KB |
Output is correct |
| 21 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 22 |
Correct |
9 ms |
6656 KB |
Output is correct |
| 23 |
Correct |
9 ms |
6656 KB |
Output is correct |
| 24 |
Correct |
9 ms |
6656 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 2 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 4 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 5 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 6 |
Correct |
8 ms |
6528 KB |
Output is correct |
| 7 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 8 |
Correct |
7 ms |
6656 KB |
Output is correct |
| 9 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 10 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 11 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 12 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 13 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 14 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 15 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 16 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 17 |
Correct |
9 ms |
6656 KB |
Output is correct |
| 18 |
Correct |
9 ms |
6656 KB |
Output is correct |
| 19 |
Correct |
10 ms |
6656 KB |
Output is correct |
| 20 |
Correct |
9 ms |
6656 KB |
Output is correct |
| 21 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 22 |
Correct |
9 ms |
6656 KB |
Output is correct |
| 23 |
Correct |
9 ms |
6656 KB |
Output is correct |
| 24 |
Correct |
9 ms |
6656 KB |
Output is correct |
| 25 |
Correct |
29 ms |
7296 KB |
Output is correct |
| 26 |
Correct |
65 ms |
8572 KB |
Output is correct |
| 27 |
Correct |
178 ms |
11500 KB |
Output is correct |
| 28 |
Correct |
178 ms |
14064 KB |
Output is correct |
| 29 |
Correct |
131 ms |
10480 KB |
Output is correct |
| 30 |
Correct |
216 ms |
14060 KB |
Output is correct |
| 31 |
Incorrect |
294 ms |
14060 KB |
Output isn't correct |
| 32 |
Halted |
0 ms |
0 KB |
- |
