제출 #1033552

#제출 시각아이디문제언어결과실행 시간메모리
1033552DucNguyen2007Pinball (JOI14_pinball)C++14
100 / 100
197 ms26384 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define pii pair<int,int> #define pll pair<ll,ll> #define fi first #define se second const int maxN=1e5+5,LIMIT=1e6+5; const ll inf=2e18; int n,m,a[maxN+1],b[maxN+1],c[maxN+1]; ll d[maxN+1],dp[maxN+1],f[maxN+1]; vector<int> cprs; bool intersect(ll l,ll r,ll mid) { return (l<=mid&&mid<=r); } struct segment { ll sum[4*LIMIT+1]; void Build(int x,int low,int high) { if(low==high) { sum[x]=inf; return; } int mid=(low+high)/2; Build(2*x,low,mid); Build(2*x+1,mid+1,high); sum[x]=min(sum[2*x],sum[2*x+1]); } int pos,l,r; ll val; void Update(int x,int low,int high) { if(low==high) { sum[x]=min(sum[x],val); return; } int mid=(low+high)/2; if(pos<=mid) { Update(2*x,low,mid); } else Update(2*x+1,mid+1,high); sum[x]=min(sum[2*x],sum[2*x+1]); } void update_val(int pos,ll val) { this->pos=pos; this->val=val; Update(1,1,cprs.size()); } ll get(int x,int low,int high) { if(low>r||high<l) { return inf; } if(low>=l&&high<=r) { return sum[x]; } int mid=(low+high)/2; ll get1=get(2*x,low,mid); ll get2=get(2*x+1,mid+1,high); return min(get1,get2); } ll query(int l,int r) { this->l=l; this->r=r; return get(1,1,cprs.size()); } }st1,st2; int nen(int x) { return lower_bound(cprs.begin(),cprs.end(),x)-cprs.begin()+1; } int main() { //freopen("","r",stdin); //freopen("","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>m>>n; for(int i=1;i<=m;i++) { cin>>a[i]>>b[i]>>c[i]>>d[i]; cprs.push_back(a[i]); cprs.push_back(b[i]); cprs.push_back(c[i]); dp[i]=inf; f[i]=inf; } cprs.push_back(1); cprs.push_back(n); sort(cprs.begin(),cprs.end()); cprs.resize(unique(cprs.begin(),cprs.end())-cprs.begin()); for(int i=1;i<=m;i++) { a[i]=nen(a[i]); b[i]=nen(b[i]); c[i]=nen(c[i]); } st1.Build(1,1,cprs.size()); st2.Build(1,1,cprs.size()); st1.update_val(nen(1),0); st2.update_val(nen(n),0); dp[0]=0; f[0]=0; for(int i=1;i<=m;i++) { ll tmp1=st1.query(a[i],b[i]); ll tmp2=st2.query(a[i],b[i]); dp[i]=min(dp[i],tmp1+d[i]); f[i]=min(f[i],tmp2+d[i]); st1.update_val(c[i],dp[i]); st2.update_val(c[i],f[i]); //cout<<i<<" "<<dp[i]<<" "<<f[i]<<'\n'; } ll ans=inf; for(int i=1;i<=m;i++) { ans=min(ans,dp[i]+f[i]-d[i]); } if(ans==inf) { cout<<-1; } else cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...