Submission #1246621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246621		Zbyszek99	Long Distance Coach (JOI17_coach)	C++20	100 / 100	184 ms	26452 KiB

coach

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<long long>
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
//mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

ll D[200002];
ll C[200002];
ll C_pref[200002];
int when_stop[200002];
ll dp[200002];

struct line
{
    ll a,b;
    bool is = 1;
    __int128_t operator()(ll x)
    {
        if(is == 0) return 5e18;
        return (__int128_t)a*x+(__int128_t)b;
    }
};

struct lichao
{
    ll l = 0;
    ll r = (1LL << 40LL);
    line best = {(ll)1e18+2137,(ll)1e18,0};
    lichao* left = NULL;
    lichao* right = NULL;
    void add_line(line line)
    {
        if(best.is == 0) 
        {
            best = line;
            return;
        }
        ll mid = (l+r)/2;
        if(line(mid) < best(mid)) swap(best,line);
        if(l == r) return;
        if(line.a > best.a)
        {
            if(left == NULL)
            {
                left = new lichao;
                left -> l = l;
                left -> r = mid-1;
            }
            if(left -> l <= left -> r)
            {
                left -> add_line(line);
            }
        }
        else
        {
            if(right == NULL)
            {
                right = new lichao;
                right -> l = mid+1;
                right -> r = r;
            }
            if(right -> l <= right -> r)
            {
                right -> add_line(line);
            }
        }
    }
    ll get_val(ll x)
    {
        if(x <= (l+r)/2) return min((ll)best(x),(left != NULL ? left -> get_val(x) : (ll)3e18));
        else return min((ll)best(x),(right != NULL ? right -> get_val(x) : (ll)3e18));
    }
};

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random();
    ll X,n,m,W,T;
    cin >> X >> n >> m >> W >> T;
    vl S(n);
    rep(i,n) cin >> S[i];
    rep(i,m) cin >> D[i] >> C[i];
    vector<pll> pas;
    rep(i,m) pas.pb({D[i],C[i]});
    pas.pb({0,(ll)3e18});
    sort(all(pas));
    S.pb(X);
    sort(all(S));
    m++;
    rep(i,m) 
    {
        D[i+1] = pas[i].ff;
        C[i+1] = pas[i].ss;
    }
    ll drinks = (X-D[m-1]+T-1)/T;
    ll ans = 0;
    rep2(i,1,m)
    {
        ll my_drinks = (X-D[i]+T-1)/T;
        ans += my_drinks*W;
        if(my_drinks != drinks)
        {
            C[i] -= W;
        }
    }
    int cur = 0;
    rep2(i,1,m) when_stop[i] = 1e9;
    forall(it,S)
    {
        int mod = it%T;
        int l = 1;
        int r = m;
        int ans = 1;
        while(l <= r)
        {
            int mid = (l+r)/2;
            if(D[mid] <= mod)
            {
                ans = mid;
                l = mid+1;
            }
            else
            {
                r = mid-1;
            }
        }
        when_stop[ans] = min(when_stop[ans],cur);
        cur++;
    }
    rep2(i,1,m) C_pref[i] = C_pref[i-1] + C[i]; 
    lichao tree;
    rep2(i,1,m)
    {
        dp[i] = dp[i-1];
        if(when_stop[i] != 1e9)
        {
            ll my_poz = S[when_stop[i]] - (S[when_stop[i]]-D[i]+T)%T;
            ll rest = (X-my_poz+T-1)/T;
            if((X-D[i]+T-1)/T != drinks) rest--;
            dp[i] = min(dp[i],tree.get_val(rest)-W*i*rest+C_pref[i]);
            // dp[i] = min(dp[i],(dp[j]-C_pref[j])+(-W*i*rest+C_pref[i]) + W*j*rest);
        }
        line new_line = {W*i,dp[i]-C_pref[i]};
        tree.add_line(new_line);
    }
    cout << ans+dp[m];
}

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