#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int m,n;
const int N=1e5+7;
int lef[N],rig[N],md[N];
long long cost[N],costleft[N],costright[N],it[15*N],ans=1e15;
map <int,int> vis;
vector <int> val;
void lw(int x){
vis[x]++;
if(vis[x]==1) val.pb(x);
}
void init(int k,int l,int r){
if(l==r){
it[k]=1e15;
return;
}
int mid=(l+r)/2;
init(k*2,l,mid);
init(k*2+1,mid+1,r);
it[k]=1e15;
}
void upd(int k,int l,int r,int pos,long long vl){
if(l>pos || r<pos || l>r) return;
if(l==r && l==pos){
it[k]=min(it[k],vl);
return;
}
int mid=(l+r)/2;
upd(k*2,l,mid,pos,vl);
upd(k*2+1,mid+1,r,pos,vl);
it[k]=min(it[k*2],it[k*2+1]);
}
long long get(int k,int l,int r,int L,int R){
if(l>R || r<L || l>r) return 1e15;
if(l>=L && r<=R) return it[k];
int mid=(l+r)/2;
return min(get(k*2,l,mid,L,R),get(k*2+1,mid+1,r,L,R));
}
int main(){
scanf("%d %d",&m,&n);
lw(1);
lw(n);
for(int i=1;i<=m;i++){
scanf("%d %d %d %lld",&lef[i],&rig[i],&md[i],&cost[i]);
lw(lef[i]);
lw(rig[i]);
lw(md[i]);
}
sort(val.begin(),val.end());
int cnt=0;
for(auto x:val){
cnt++;
vis[x]=cnt;
}
for(int i=1;i<=m;i++){
lef[i]=vis[lef[i]];
rig[i]=vis[rig[i]];
md[i]=vis[md[i]];
}
init(1,1,cnt);
for(int i=1;i<=m;i++){
costleft[i]=get(1,1,cnt,lef[i],rig[i]);
if(lef[i]==1) costleft[i]=0;
//cout<<costleft[i]<<endl;
upd(1,1,cnt,md[i],costleft[i]+cost[i]);
}
init(1,1,cnt);
for(int i=1;i<=m;i++){
costright[i]=get(1,1,cnt,lef[i],rig[i]);
if(rig[i]==cnt) costright[i]=0;
ans=min(ans,costleft[i]+costright[i]+cost[i]);
upd(1,1,cnt,md[i],costright[i]+cost[i]);
}
if(ans==1e15) printf("-1");
else printf("%lld",ans);
}
Compilation message
pinball.cpp: In function 'int main()':
pinball.cpp:42:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&m,&n);
^
pinball.cpp:46:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %lld",&lef[i],&rig[i],&md[i],&cost[i]);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
17260 KB |
Output is correct |
2 |
Correct |
0 ms |
17260 KB |
Output is correct |
3 |
Correct |
0 ms |
17260 KB |
Output is correct |
4 |
Correct |
0 ms |
17260 KB |
Output is correct |
5 |
Correct |
0 ms |
17260 KB |
Output is correct |
6 |
Correct |
0 ms |
17260 KB |
Output is correct |
7 |
Correct |
0 ms |
17260 KB |
Output is correct |
8 |
Correct |
0 ms |
17260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
17260 KB |
Output is correct |
2 |
Correct |
0 ms |
17260 KB |
Output is correct |
3 |
Correct |
0 ms |
17260 KB |
Output is correct |
4 |
Correct |
0 ms |
17260 KB |
Output is correct |
5 |
Correct |
0 ms |
17260 KB |
Output is correct |
6 |
Correct |
0 ms |
17260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
17260 KB |
Output is correct |
2 |
Correct |
0 ms |
17260 KB |
Output is correct |
3 |
Correct |
3 ms |
17396 KB |
Output is correct |
4 |
Correct |
0 ms |
17260 KB |
Output is correct |
5 |
Correct |
3 ms |
17396 KB |
Output is correct |
6 |
Correct |
0 ms |
17392 KB |
Output is correct |
7 |
Correct |
0 ms |
17396 KB |
Output is correct |
8 |
Correct |
3 ms |
17396 KB |
Output is correct |
9 |
Correct |
3 ms |
17396 KB |
Output is correct |
10 |
Correct |
3 ms |
17396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
18212 KB |
Output is correct |
2 |
Correct |
146 ms |
20188 KB |
Output is correct |
3 |
Correct |
429 ms |
22556 KB |
Output is correct |
4 |
Correct |
243 ms |
17396 KB |
Output is correct |
5 |
Correct |
346 ms |
22028 KB |
Output is correct |
6 |
Correct |
383 ms |
18212 KB |
Output is correct |
7 |
Correct |
926 ms |
26104 KB |
Output is correct |
8 |
Correct |
639 ms |
23480 KB |
Output is correct |
9 |
Correct |
83 ms |
20320 KB |
Output is correct |
10 |
Correct |
366 ms |
25312 KB |
Output is correct |
11 |
Correct |
479 ms |
33332 KB |
Output is correct |
12 |
Correct |
946 ms |
33332 KB |
Output is correct |
13 |
Correct |
846 ms |
33332 KB |
Output is correct |
14 |
Correct |
849 ms |
33332 KB |
Output is correct |