This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=2e5+5;
vector<int> cor;
ll segtree[nax*4][2];
void build(int pos,int l,int r){
if(l==r){
segtree[pos][0]=1e18;
segtree[pos][1]=1e18;
return;
}
int mid=(r+l)/2;
build(pos*2+1,l,mid);
build(pos*2+2,mid+1,r);
segtree[pos][0]=min(segtree[pos*2+1][0],segtree[pos*2+2][0]);
segtree[pos][1]=min(segtree[pos*2+1][1],segtree[pos*2+2][1]);
return;
}
void update1(int pos,int l,int r,int index,ll value){
if(l==r){
segtree[pos][0]=min(segtree[pos][0],value);
return;
}
int mid=(r+l)/2;
if(index<=mid) update1(pos*2+1,l,mid,index,value);
else update1(pos*2+2,mid+1,r,index,value);
segtree[pos][0]=min(segtree[pos*2+1][0],segtree[pos*2+2][0]);
return;
}
void update2(int pos,int l,int r,int index,ll value){
if(l==r){
segtree[pos][1]=min(segtree[pos][1],value);
return;
}
int mid=(r+l)/2;
if(index<=mid) update2(pos*2+1,l,mid,index,value);
else update2(pos*2+2,mid+1,r,index,value);
segtree[pos][1]=min(segtree[pos*2+1][1],segtree[pos*2+2][1]);
return;
}
ll query1(int pos,int l,int r,int left,int right){
if(l>r||l>right||r<left) return 1e18;
else if(l>=left&&r<=right) return segtree[pos][0];
int mid=(r+l)/2;
return min(query1(pos*2+1,l,mid,left,right),query1(pos*2+2,mid+1,r,left,right));
}
ll query2(int pos,int l,int r,int left,int right){
if(l>r||l>right||r<left) return 1e18;
else if(l>=left&&r<=right) return segtree[pos][1];
int mid=(r+l)/2;
return min(query2(pos*2+1,l,mid,left,right),query2(pos*2+2,mid+1,r,left,right));
}
int main(){
int n,m;
cin>>n>>m;
ll a[n],b[n],c[n],d[n];
set<int> st;
st.insert(1);
st.insert(m);
for (int i = 0; i < n; ++i)
{
cin>>a[i]>>b[i]>>c[i]>>d[i];
st.insert(a[i]);
st.insert(b[i]);
st.insert(c[i]);
}
for(auto u:st) {
cor.pb(u);
}
build(0,0,cor.size()-1);
update1(0,0,cor.size()-1,0,0);
update2(0,0,cor.size()-1,cor.size()-1,0);
ll ans[cor.size()][2];
for (int i = 0; i < cor.size(); ++i)
{
ans[i][0]=ans[i][1]=1e18;
}
ll res=1e18;
for (int i = 0; i < n; ++i)
{
int l=lower_bound(cor.begin(),cor.end(),a[i])-cor.begin();
int r=lower_bound(cor.begin(),cor.end(),b[i])-cor.begin();
int cur=lower_bound(cor.begin(),cor.end(),c[i])-cor.begin();
//cout <<l<<" "<<r<<" "<<cur<<endl;
if(a[i]==1){
ans[cur][0]=min(ans[cur][0]+d[i],d[i]);
}
if(b[i]==m){
ans[cur][1]=min(ans[cur][1]+d[i],d[i]);
}
ll left=query1(0,0,cor.size()-1,l,r);
ll right=query2(0,0,cor.size()-1,l,r);
//cout <<left<<" "<<right<<" "<<d[i]<<endl;
//cout <<ans[cur][0]<<" "<<ans[cur][1]<<" "<<d[i]<<endl;
ans[cur][0]=min(ans[cur][0],d[i]+left);
ans[cur][1]=min(ans[cur][1],d[i]+right);
update1(0,0,cor.size()-1,cur,ans[cur][0]);
update2(0,0,cor.size()-1,cur,ans[cur][1]);
//cout <<ans[cur][0]<<" "<<ans[cur][1]<<" "<<d[i]<<endl;
res=min(res,ans[cur][0]+ans[cur][1]-d[i]);
//cout <<res<<endl;
}
if(res>=1e17) cout <<-1<<endl;
else cout <<res<<endl;
}
Compilation message (stderr)
pinball.cpp: In function 'int main()':
pinball.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int i = 0; i < cor.size(); ++i)
| ~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |