# 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,tree[4*N];
void update(int node, int le, int ri ,int idx, int val) {
if (le>idx || ri<idx) return;
if (le==ri) {
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]);
}
int getans(int node, int le, int ri ,int start, int end) {
if (le>end || ri<start) return 1e9;
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];
}
for (int i=1; i<=4*n; i++) {
tree[i]=1e9;
}
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]=1e9;
}
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];
// cout<<dp1[5]<<endl;
update(1,1,n,c[i],dp1[i]);
}ans=1e9;
for (int i=1; i<=m; i++) {
ans=min(ans, dp[i]+dp1[i]-d[i]);
}
if (ans==1e9) cout<<-1<<endl;else
cout<<ans<<endl;
}
| # |
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 |
- |
