제출 #122027

#제출 시각아이디문제언어결과실행 시간메모리
122027shayan_pLong Distance Coach (JOI17_coach)C++14
71 / 100
2045 ms14220 KiB
// High above the clouds there is a rainbow... #include<bits/stdc++.h> #define F first #define S second #define PB push_back #define sz(s) int((s).size()) #define bit(n,k) (((n)>>(k))&1) #define real STH_STRANGE using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef long double ld; const int maxn=2e5+10,mod=1e9+7, SQ1=205, SQ2=1000; const ll inf=1e18; ll a[maxn], d[maxn], dp[maxn], W, T; pll p[maxn]; pair<ll,int> upd[maxn]; vector<pll> cht[SQ2], real[SQ2]; ll lz1[SQ2], lz2[SQ2];// tedad jaam // tedad prefix jaam bool bad(pll a,pll b,pll c){ return ld(a.S-b.S) / ld(b.F-a.F) >= ld(b.S-c.S) / ld(c.F-b.F); } ll gety(pll p,ll x){ return p.F*x + p.S; } void add(vector<pll>&v, ll a,ll b){ if(sz(v) && v.back().F == a){ if( v.back().S <= b ) return; v.pop_back(); } while(sz(v)>1 && bad(v[sz(v)-2], v[sz(v)-1], {a,b} ) ) v.pop_back(); v.PB({a,b}); } ll ask(vector<pll>&v, ll x){ assert(sz(v)); int l=0,r=sz(v); while(r-l>2){ int mid=(l+r+1)>>1; if(gety(v[mid-1],x) < gety(v[mid],x) ) r=mid; else l=mid; } if(r-l==1) return gety(v[l],x); return min( gety(v[l],x), gety(v[l+1],x) ); } void relax(int id){ cht[id].clear(); for(auto &x:real[id]) x.S+= x.F * lz2[id] + lz1[id]; lz1[id]=lz2[id]=0; } void build(int id){ for(auto x:real[id]) add(cht[id], x.F, x.S); } void add(int f,int s,ll x){ if(f>=s) return; int id=f/SQ1; relax(id); for(int i=0;i<id;i++) lz1[i]+= x*(s-f); for(int i=0;i<sz(real[id]);i++) real[id][i].S+= x* max(int(0), s-max(f,i + id*SQ1 +1)); build(id), f=SQ1* (id+1); id=s/SQ1; relax(id); int cnt=0, w=s%SQ1; while(f<s && w) real[id][s-1- id*SQ1].S+= x*cnt, cnt++, s--, w--; build(id); if(f>=s) return; f/=SQ1, s/=SQ1; while(f<s) cnt+=SQ1, lz1[s-1]+=x* cnt, lz2[s-1]+=x, s--; } ll ask(){ ll ans=inf; for(int i=0;i<SQ2;i++){ if(sz(cht[i])) ans=min(ans, ask(cht[i],lz2[i]) + lz1[i]); } return ans; } int main(){ ios_base::sync_with_stdio(false);cin.tie(0); ll x; int n,m; cin>>x>>n>>m>>W>>T; for(int i=0;i<n;i++){ cin>>a[i]; } sort(a,a+n); a[n++]=x; ll ans=W*((x/T)+1); p[0]={0,inf}, d[0]=0; for(int i=1;i<=m;i++){ cin>>p[i].F>>p[i].S; d[i]=p[i].F; p[i].S-= W* (x/T), ans+= W* (x/T); if( (p[i].F%T) < (x%T) ) p[i].S-= W, ans+=W; } m++; sort(p,p+m), sort(d,d+m); for(int i=0;i<=m;i++){ upd[i]={inf,0}; } ll lst=0; for(int i=0;i<n;i++){ int A=lower_bound(d,d+m,lst %T)-d, B=lower_bound(d,d+m,a[i] %T)-d; if( lst< (a[i]/T)*T ) A=0; if(A!=B) upd[B]= min(upd[B], {a[i]/T,A} ); lst=a[i]; } real[0].PB({-1,0}); build(0); vector< pair<pii,ll> >v; for(int i=1;i<=m;i++){ if(upd[i].F!=inf){ pair<ll,int>p=upd[i]; if(sz(v)==0){ assert(p.S==0); add(0,i, W*p.F); v.PB({{0,i},p.F}); } else{ add(v.back().F.S, i, W* p.F); while(sz(v) && p.F<v.back().S) add(v.back().F.F, v.back().F.S, W*( p.F- v.back().S) ), v.pop_back(); v.PB({ {v.back().F.S,i}, p.F}); } } dp[i]=dp[i-1]; if(sz(v) && v.back().F.S==i) dp[i]= ask(); for(int j=0;j<SQ2;j++) lz1[j]+= p[i].S; relax(i/SQ1); real[i/SQ1].PB({-(i%SQ1)-1,dp[i]}); build(i/SQ1); } return cout<<dp[m]+ans<<endl,0; } // Deathly mistakes: // * Read the problem curfully. // * Check maxn // * Overflows.
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...