제출 #122054

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
122054		shayan_p	Long Distance Coach (JOI17_coach)	C++14	0 / 100	3 ms	384 KiB

coach

// 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=500, SQ2=(maxn/SQ1) + 5;
const ll inf=1e18;
 
ll a[maxn], d[maxn], dp[maxn], W, T;
pll p[maxn];
ll upd[maxn]; 
 
vector<pair<pll,int> > cht[SQ2], vv;

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< pair<pll,int> >&v, ll a,ll b,int i){
    if(sz(v) && v.back().F.F == a){
	if( v.back().F.S <= b ) return;
	v.pop_back();
    }
    while(sz(v)>1 && bad(v[sz(v)-2].F, v[sz(v)-1].F, {a,b} ) ) v.pop_back();
    v.PB({{a,b},i});
}
ll ask(vector<pair<pll,int> >&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].F,x) < gety(v[mid].F,x) ) r=mid;
	else l=mid;
    }
    if(r-l==1) return gety(v[l].F,x);
    return min( gety(v[l].F,x), gety(v[l+1].F,x) );
}
 
 
void relax(int id){
    for(auto &x:cht[id])
	x.F.S+= x.F.F * lz2[id] + lz1[id];
    lz1[id]=lz2[id]=0;
    vv=cht[id], cht[id].clear();
}
void build(int id){
    for(auto x:vv)
	add(cht[id], x.F.F, x.F.S, 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(vv);i++) vv[i].S+= x* max(int(0), s-max(f,vv[i].S + 1));
    build(id), f=SQ1* (id+1);

    if(f>=s) return;
    
    id=s/SQ1;
    
    relax(id);
    int cnt=0;
    for(int i=sz(vv)-1;i>=0;i--){
	vv[i].F.S+= x*cnt;
	cnt+= vv[i].S < s;
    }
    build(id), s=SQ1 * 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;

    #ifdef shayan
    //   srand(time(0));
    x=1e12, n=2e5, m=2e5, W=513051, T=1010;
    #else
    cin>>x>>n>>m>>W>>T;
    #endif
    
    for(int i=0;i<n;i++){
	#ifdef shayan
	a[i]= 1ll* (rand()%999) * (rand()%1000000) + 1;
	#else
	cin>>a[i];
	#endif
    }
    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++){
	#ifdef shayan
	p[i].F= rand(), p[i].S= rand();
	#else
	cin>>p[i].F>>p[i].S;
	#endif
	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;
    }
    
    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 );
	lst=a[i];
    }
 
    add(cht[0], -1, 0, 0);
    
    vector< pair<pii,ll> >v;

    int pt=0;
    
    for(int i=1;i<=m;i++){
	if(upd[i]!=inf){
	    if(sz(v)==0){
		v.PB({{0,i},upd[i]});
	    }
	    else{
		while(sz(v) && upd[i]<v.back().S) add(v.back().F.F, v.back().F.S, W*( upd[i]- v.back().S) ), v.pop_back();
		v.PB({ {v.back().F.S,i}, upd[i]});
	    }
	}
	dp[i]=dp[i-1];
	if(sz(v) && v.back().F.S==i) dp[i]= ask();

	pt=max(pt,i+1);
	while(pt<=m && upd[pt]==inf) pt++;
 	
	for(int j=0;j<SQ2;j++)
	    lz1[j]+= p[i].S + W* (pt<=m ? upd[pt] : 0);
	
	int aa= -(i%SQ1)-1, id=i/SQ1;	
	add(cht[id], aa, dp[i]- aa*lz2[id] - lz1[id], i);
    }
    return cout<<dp[m]+ans<<endl,0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn
//  * Overflows.

• Subtask 1: 0 / 16
• Subtask 2: 0 / 30
• Subtask 3: 0 / 25
• Subtask 4: 0 / 29