#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <climits>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cassert>
#include <vector>
#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define For( i , a ) for(int i=1;i<=a;i++)
#define ort (b+s)/2
#define y2 asrwjaelkf
#define y1 asseopirwjaelkf
#define set multiset
using namespace std;
inline int read() {
int res = 0 ;int neg ;
while(true){char ch = getchar();if(ch>='0' && ch<='9' || ch=='-'){if(ch=='-') neg = -1;else neg = 1 , res = ch-'0';break;} }
while(true){char ch = getchar();if(ch>='0' && ch<='9') res*=10 , res+=ch-'0';else break;}
return res*neg;
}
typedef long long Lint;
typedef double db;
typedef pair<int,int> ii;
typedef pair<db,db> dd;
typedef pair<db,int> di;
typedef pair<ii,int> iii;
typedef pair<ii,ii> i4;
const int maxn = 100020;
const int maxm = 1000020;
const int MOd = 1e9 + 7;
Lint segment[maxn*3][2];
int n, a, b;
int l[maxn], r[maxn], c[maxn], ar[maxn];
vector<int> v;
void up( int x, Lint t, int tp ) {
umin( segment[x+n-1][tp], t );
for(int k=(x+n-1)>>1;k;k>>=1) segment[k][tp] = min( segment[k+k][tp], segment[k+k+1][tp] );
}
Lint find( int l, int r, int tp ) {
Lint ret = 1e18;
for( l+=n-1, r+=n-1; l <= r; l=(l+1)>>1, r = (r-1)>>1 ) {
if( l&1 ) umin( ret, segment[l][tp] );
if( ~r&1 ) umin( ret, segment[l][tp] );
}
return ret;
}
int main() {
//freopen("asd.in","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d %d",&a,&b);
v.pb( 1 );
v.pb( b );
for(int i=1;i<=a;i++) {
scanf("%d %d %d %d",&l[i],&r[i],&c[i],&ar[i]);
v.pb( c[i] );
}
sort( all( v ) );
v.erase( unique( all( v ) ), v.end() );
n = 1;
while( n < v.size() ) n <<= 1;
for(int i=1;i<n+n;i++) segment[i][0] = segment[i][1] = 1e18;
up( 1, 0, 0 );
up( v.size(), 0, 1 );
//for(int i=0;i<v.size();i++) printf("asd %d\n",v[i]);
Lint ans = 1e18;
for(int i=1;i<=a;i++) {
int o = lower_bound( all( v ), c[i] ) - v.begin() + 1;
int j = lower_bound( all( v ), l[i] ) - v.begin() + 1;
int k = upper_bound( all( v ), r[i] ) - v.begin();
Lint ll = find( j, k, 0 );
Lint rr = find( j, k, 1 );
up( o, ll+ar[i], 0 );
up( o, rr+ar[i], 1 );
umin( ans, ll+rr+ar[i] );
}
if( ans >= 1e18 ) ans = -1;
cout << ans << endl;
return 0;
}
Compilation message
pinball.cpp: In function 'int read()':
pinball.cpp:31:48: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
while(true){char ch = getchar();if(ch>='0' && ch<='9' || ch=='-'){if(ch=='-') neg = -1;else neg = 1 , res = ch-'0';break;} }
^
pinball.cpp: In function 'int main()':
pinball.cpp:84:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while( n < v.size() ) n <<= 1;
^
pinball.cpp:73:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&a,&b);
^
pinball.cpp:77:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d",&l[i],&r[i],&c[i],&ar[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
8272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
8272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
8272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
8412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
