Submission #997086

#TimeUsernameProblemLanguageResultExecution timeMemory
997086MarwenElarbiPinball (JOI14_pinball)C++17
0 / 100
1 ms348 KiB
#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]=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]=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]); } if(b[i]==m){ ans[cur][1]=min(ans[cur][1],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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...