# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N=3e5+5;
long long dp[N],dp1[N],n,m,a[N],b[N],c[N],d[N],ans,cnt;
map <long long, long long> tree,xx;
vector <long long> v;
void update(long long node, long long le, long long ri ,long long idx, long long val) {
if (le>idx || ri<idx) return;
if (le==ri) {
tree[node]=min(tree[node],val);
return ;
}
int mid=(le+ri)/2;
update(2*node, le ,mid, idx, val);
update(2*node+1, mid+1, ri, idx, val);
tree[node]=min(tree[2*node],tree[2*node+1]);
}
long long getans(long long node, long long le, long long ri ,long long start, long long end) {
if (le>end || ri<start) return 1e17;
if (le>=start && ri<=end) {
return tree[node];
}
int mid=(le+ri)/2;
return min(getans(2*node, le ,mid, start, end),getans(2*node+1, mid+1, ri, start,end));
}
int main() {
cin>>m>>n;
for (int i=1; i<=m; i++) {
cin>>a[i]>>b[i]>>c[i]>>d[i];
v.pb(a[i]);
v.pb(b[i]);
v.pb(c[i]);
}
sort(v.begin(), v.end());
xx[v[0]]=1;
cnt=1;
for (int i=1; i<v.size(); i++) {
if (v[i]!=v[i-1]) {
cnt++;
xx[v[i]]=cnt;
}
}
for (int i=1; i<=n; i++){
a[i]=xx[a[i]];
b[i]=xx[b[i]];
c[i]=xx[c[i]];
}
for (int i=1; i<=4*n; i++) {
tree[i]=1e17;
}
for (int i=1; i<=m; i++) {
if (a[i]==1) {
dp[i]=d[i];
update(1,1,n,c[i],dp[i]);
continue;
}
dp[i]=getans(1,1,n,a[i],b[i])+d[i];
update(1,1,n,c[i],dp[i]); //cout<<dp[5]<<endl;
}
for (int i=1; i<=4*n; i++) {
tree[i]=1e17;
}
for (int i=1; i<=m; i++) {
if (b[i]==n) {
dp1[i]=d[i];
update(1,1,n,c[i],dp1[i]);
continue;
}
dp1[i]=getans(1,1,n,a[i],b[i])+d[i];
update(1,1,n,c[i],dp1[i]);
}
ans=1e17;
for (int i=1; i<=m; i++) {
// cout<<dp[i]<<" "<<dp1[i]<<" "<<dp1[i]-d[i]<<" "<<d[i]<<" "<<dp[i]+dp1[i]-d[i]<<endl;
ans=min(ans, dp[i]+dp1[i]-d[i]);
}
if (ans==1e17) cout<<-1<<endl;else
cout<<ans<<endl;
}
Compilation message
pinball.cpp: In function 'int main()':
pinball.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for (int i=1; i<v.size(); i++) {
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
