Submission #699384

#	Time	Username	Problem	Language	Result	Execution time	Memory
699384		urosk	Long Distance Coach (JOI17_coach)	C++14	100 / 100	232 ms	19040 KiB

coach

#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 1000000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
//using namespace __gnu_pbds;
/*
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}
*/
#define ull __int128
#define maxn 200005
#define maxx 1000005
ll x,n,m,w,ti;
ll mx = 1000000000000;
ll s[maxn],ps[maxn],mn[maxn],dp[maxn];
pll a[maxn];
struct line{
    ll n,k;
    line(){}
    line(ll a,ll b){k = a;n = b;}
    ull operator()(ll x){return ull(k)*ull(x)+ull(n);}
};
line t[maxx];
ll ls[maxx],rs[maxx],root = 0,tsz = 0;
ull get(ll v,ll tl,ll tr,ll i){
    if(!v) return ull(llinf);
    if(tl==tr) return t[v](i);
    ll mid = (tl+tr)/2;
    if(i<=mid) return min(t[v](i),get(ls[v],tl,mid,i));
    return min(t[v](i),get(rs[v],mid+1,tr,i));
}
void upd(ll &v,ll tl,ll tr,line f){
    if(!v){v = ++tsz;t[v] = f;return;}
    line g = t[v];
    if(tl==tr){
        if(f(tl)<g(tl)) t[v] = f;
        return;
    }
    ll mid = (tl+tr)/2;
    if(f(tl)>g(tl)) swap(f,g);
    ull fl = f(tl), fm = f(mid);
    ull gl = f(tl), gm = g(mid);
    if(fm<=gm){t[v] = f; upd(rs[v],mid+1,tr,g);}
    else{t[v] = g; upd(ls[v],tl,mid,f);}
}
void tc(){
    cin >> x >> n >> m >> w >> ti;
    for(ll i = 1;i<=n;i++) cin >> s[i]; s[++n] = x;
    for(ll i = 1;i<=m;i++) cin >> a[i].fi >> a[i].sc;
    sort(a+1,a+1+m);
    for(ll i = 1;i<=m;i++) mn[i] = llinf;
    for(ll i = 1;i<=m;i++) ps[i] = ps[i-1] + a[i].sc;
    for(ll i = 1;i<=n;i++){
        pll p = {s[i]%ti,llinf};
        ll j = upper_bound(a+1,a+1+m,p) - a - 1;
        mn[j] = min(mn[j],s[i]/ti);
    }
    dp[0] = (x/ti+1)*w;
    upd(root,0,mx,line(0,dp[0]));
    for(ll i = 1;i<=m;i++){
        dp[i] = dp[i-1] + ((x-a[i].fi)/ti+1)*w;
        if(mn[i]!=llinf) dp[i] = min(dp[i],(ll)get(root,0,mx,mn[i])+ps[i]+i*w*mn[i]);
        upd(root,0,mx,line(-i*w,dp[i]-ps[i]));
    }
    cout<<dp[m]<<endl;
}
int main(){
	daj_mi_malo_vremena
    int t; t = 1;
    while(t--){
        tc();
    }
	return 0;
}

Compilation message (stderr)

coach.cpp: In function 'void upd(long long int&, long long int, long long int, line)':
coach.cpp:79:9: warning: unused variable 'fl' [-Wunused-variable]
   79 |     ull fl = f(tl), fm = f(mid);
      |         ^~
coach.cpp:80:9: warning: unused variable 'gl' [-Wunused-variable]
   80 |     ull gl = f(tl), gm = g(mid);
      |         ^~
coach.cpp: In function 'void tc()':
coach.cpp:86:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   86 |     for(ll i = 1;i<=n;i++) cin >> s[i]; s[++n] = x;
      |     ^~~
coach.cpp:86:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   86 |     for(ll i = 1;i<=n;i++) cin >> s[i]; s[++n] = x;
      |                                         ^

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