Submission #1210493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210493		og_matveychick1	Long Distance Coach (JOI17_coach)	C++20	46 / 100	22 ms	10308 KiB

coach

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

// /*
//                                                //////////**DEFINES - START**//////////

#define ret return
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()
#define be(x) x.begin()
#define en(x) x.end()
#define sz(x) ll(x.size())
#define for0(i, n) for (ll   i = 0; i < (n); ++i)
#define for1(i, n) for (ll   i = 1; i < (n); ++i)
#define rfor0(i, n) for (ll   i = (n) - 1; i >= 0; --i)
#define rfor1(i, n) for (ll   i = (n) - 1; i >= 1; --i)
#define rep(i, a, n) for (ll   i = a; i < ll(n); ++i)
#define rrep(i, a, n) for (ll   i = a - 1; i >= ll(n); --i)
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define fastIO() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define con continue
#define pb push_back
#define pob pop_back
#define deb(x) cout << (#x) << " is " << (x) << endl
#define ins insert
#define len(s) (s).length()
#define gi greater<int>()
#define gll greater<ll  >()
#define gstr greater<string>()
#define gpll greater<pair<ll  , ll  >>()
#define rast(x1, y1, x2, y2) sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
#define rev reverse
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define rs resize
#define last(a) a.back()
#define co count
#define ba(a) a.back()
#define um unordered_map
#define rsun(a) a.resize(unique(a.begin(), a.end())-a.begin())
#define endl '\n'
#ifdef OG_Matveychick1
bool local = true;
#else
bool local = false;
#endif

//                                                \\\\\\\\\\**DEFINES - END**\\\\\\\\\\
        // */

// /*
//                                                //////////**TYPEDEFS - START**//////////

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<char> vc;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<string> vs;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ull> vull;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef pair<double, double> pdd;
typedef double ld;
typedef double D;
typedef vector<ld> vld;
typedef vector<pair<ld, ld>>
        vpld;
typedef string str;
typedef set<ll> sll;
typedef set<int> si;
typedef set<str> ss;
typedef set<pii> spii;
typedef multiset<int> msi;
typedef multiset<ll> msll;
typedef multiset<str> mss;
typedef multiset<pii> mspii;
typedef multiset<pll> mspll;
typedef map<str, str> mps;
typedef map<int, int> mpi;
typedef map<ll, ll> mpll;
typedef map<int, vi> mpvi;
typedef map<int, vll> mpvll;
typedef map<char, int> mpci;
typedef multimap<ll, ll> mmpll;
typedef multimap<str, str> mmps;
typedef multimap<int, int> mmpi;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<long double>> vvld;
typedef vector<vvi> vvvi;
typedef vector<vector<char>> vvc;
typedef vector<vs> vvs;
typedef vector<D> vD;
typedef set<pair<ll, ll>>
        spll;
typedef pair<ull, ull> pull;
typedef vector<pull> vpull;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef set<char> sc;
typedef queue<int> qi;
typedef queue<ll> qll;
typedef queue<bool> qb;
typedef vector<sll> vsll;
typedef queue<pair<ll, ll>>
        qpll;
typedef vector<vector<pair<int, int>>>
        vvpii;
typedef vector<vector<pair<ll, ll>>>
        vvpll;
typedef vector<spll> vspll;
typedef multiset<char> msc;
typedef queue<str> qs;
typedef vector<set<int>> vsi;
typedef priority_queue<ll> pqll;
typedef vector<vsll> vvsll;
typedef pair<ld, ld> pld;
typedef vector<vvll> vvvll;
typedef set<ld> sld;
typedef vector<vpld> vvpld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
        ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
        ordered_multiset;

//                                                \\\\\\\\\\**TYPEDEFS - END**\\\\\\\\\\
        // */


// /*
//                                                //////////**CONSTANTS - START**//////////

const ld pi = acosl(-1);
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
const ll MAXLL = 9223372036854775807;
//const ll MAXINT = 2147483647;
const ld eps = 1e-6;

//                                                \\\\\\\\\\**CONSTANTS - END**\\\\\\\\\\
        // */


// /*
//                                                //////////**TEMPLATES - START**//////////


template<typename T>
istream &operator>>(istream &in, vector<T> &a) {
    for (T &i: a) in >> i;
    return in;
}

template<typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &a) {
    in >> a.fi >> a.se;
    return in;
}

template<typename T1, typename T2>
ostream &operator<<(ostream &out, pair<T1, T2> &a) {
    out << a.fi << " " << a.se;
    return out;
}

template<typename T1, typename T2>
istream &operator>>(istream &in, vector<pair<T1, T2>>

&a) {
    for (
        pair<T1, T2> &i
            : a)
        in >> i.fi >> i.
                se;
    return
            in;
}

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &a) {
    for (auto i: a) {
        out << i << " ";
    }
    return out;
}

template<typename T1, typename T2>
ostream &operator<<(ostream &out, vector<pair<T1, T2>>

&a) {
    for (
        pair<T1, T2> i
            : a)
        out << i.fi << " " << i.se <<
            endl;
    return
            out;
}

template<typename T1>
ostream &operator<<(ostream &out, vector<vector<T1>> &a) {
    for (vector<T1> i: a) {
        for (T1 j: i) out << j << " ";
        out << endl;
    }
    return out;
}

template<typename T1, typename T2>
inline T1 min(T1 a, T2 b) {
    b = (T1) b;
    return a > b ? b : a;
}

template<typename T1, typename T2>
inline T1 max(T1 a, T2 b) {
    b = (T1) b;
    return a > b ? a : b;
}

template<typename T1, typename T2>
inline void amin(T1 &a, T2 b) {
    a = min(a, b);
}

template<typename T1, typename T2>
inline void amax(T1 &a, T2 b) {
    a = max(a, b);
}


//                                                \\\\\\\\\\**TEMPLATES - END**\\\\\\\\\\
        // */


// This bear is a good alternative to duck!!!
/*
    ????      ??????
  ???????????????????
 ????????????????  ???
???   ???????????  ???
???  ???????????? ??
 ??????????????????
   ??????????????? ?
   ?????????????????
   ???????   ???    ??
    ????  ??????????
     ????     ?? ???
   ???????????? ?????
  ????????????????????
 ????????   ??  ???????
 ???????         ?????
 */


ld getTime() {
    return (ld) clock() / (ld) CLOCKS_PER_SEC;
}


mt19937_64 rn(chrono::steady_clock::now().time_since_epoch().count());
//mt19937_64 rn(4);

ll rnd(ll l, ll r) {
    ll a = rn() % (r - l + 1) + l;
    return a;
}

void solve();

ll T = 1;

signed main(int argc, char **argv) {
    //    setlocale(LC_ALL, "RUS");
    fastIO()
    cout.precision(12);
    cout << fixed;
    if (local && argc == 1) {
        freopen("input.txt", "r", stdin);
        //        freopen("output.txt", "w", stdout);
    }
//    cin >> T;
    while (T--) {
        solve();
    }
    if (local && argc == 1) {
        cout << endl << fixed << "time = " << getTime();
    }
    return 0;
}


/*
    ___        __              __   ______          __        _____ __             __          __  __
   /   | _____/ /___  ______ _/ /  / ____/___  ____/ /__     / ___// /_____ ______/ /______   / / / /__  ________
  / /| |/ ___/ __/ / / / __ `/ /  / /   / __ \/ __  / _ \    \__ \/ __/ __ `/ ___/ __/ ___/  / /_/ / _ \/ ___/ _ \
 / ___ / /__/ /_/ /_/ / /_/ / /  / /___/ /_/ / /_/ /  __/   ___/ / /_/ /_/ / /  / /_(__  )  / __  /  __/ /  /  __/
/_/  |_\___/\__/\__,_/\__,_/_/   \____/\____/\__,_/\___/   /____/\__/\__,_/_/   \__/____/  /_/ /_/\___/_/   \___/
*/



struct ST {
    ll n;
    vll t1, t2;

    ST(ll n) : n(n), t1(4 * n, 1e18), t2(4 * n, 1e18) {}

    void update(ll l, ll r, ll x) {
        update(1, 0, n, l, r, x);
    }

    void update(ll v, ll l, ll r, ll L, ll R, ll x) {
        if (l >= R || r <= L) ret;
        amin(t1[v], x);
        if (l >= L && r <= R) {
            amin(t2[v], x);
            ret;
        }
        ll m = (l + r) / 2;
        update(v * 2, l, m, L, R, x);
        update(v * 2 + 1, m, r, L, R, x);
    }

    ll get(ll l, ll r) {
        ret get(1, 0, n, l, r);
    }

    ll get(ll v, ll l, ll r, ll L, ll R) {
        if (l >= R || r <= L) ret 1e18;
        if (l >= L && r <= R) ret t1[v];
        ll m = (l + r) / 2;
        ret min({get(v * 2, l, m, L, R), get(v * 2 + 1, m, r, L, R), t2[v]});
    }
};

const ll N = 1e5 + 5, K = 20;

ll X, n, m, w, t, s[N], f[N];
pll a[N], sp[K][N];
ST st(N);
map<array<ll, 5>, ll> dp;

ll cost(ll i, ll x) {
    if (x == -1) ret w * ((X - a[i].fi) / t + 1);
    else
        ret w * ((x - a[i].fi) / t) + a[i].se;
}

void build() {
    for0(i, n - 1) {
        ll R;
        ll r = (s[i + 1] - 1 - a[0].fi) / t * t + a[0].fi;
        ll l = (s[i] - 1 - a[0].fi) / t * t + a[0].fi + t;
        while (r + t < s[i + 1]) r += t;
        while (l - t >= s[i]) l -= t;
        while (r >= s[i + 1]) r -= t;
        while (l < s[i]) l += t;

        ll r1;
        if (r >= s[i]) {
            r1 = 0;
            R = r;
        } else {
            ll id = lb(a, a + m, mp(s[i] % t, -1ll)) - a;
            r = (s[i + 1] - 1 - a[id].fi) / t * t + a[id].fi;
            l = (s[i] - 1 - a[id].fi) / t * t + a[id].fi + t;
            while (r + t < s[i + 1]) r += t;
            while (l - t >= s[i]) l -= t;
            while (r >= s[i + 1]) r -= t;
            while (l < s[i]) l += t;
            if (r < s[i]) con;
            else r1 = id;
        }
        ll l2 = r1, r2 = m;
        while (l2 + 1 < r2) {
            ll c = (l2 + r2) / 2;
            r = (s[i + 1] - 1 - a[c].fi) / t * t + a[c].fi;
            l = (s[i] - 1 - a[c].fi) / t * t + a[c].fi + t;
            while (r + t < s[i + 1]) r += t;
            while (l - t >= s[i]) l -= t;
            while (r >= s[i + 1]) r -= t;
            while (l < s[i]) l += t;
            (r >= R ? l2 : r2) = c;
        }
        st.update(l2, r2, i);
        f[i] = l2;
    }
    for0(i, m) sp[0][i] = {a[i].se, i};
    for0(i, K - 1) for0(j, m - (1 << (i + 1)) + 1)sp[i + 1][j] = max(sp[i][j], sp[i][j + (1 << i)]);
}

ll get(ll l, ll r) {
    ll d = __lg(r - l);
    ret max(sp[d][l], sp[d][r - (1 << d)]).se;
}

ll best(ll i, ll k, ll p) {
    ret min(k, st.get(i, p));
}

ll getx(ll j, ll i) {
    if (i == n - 1) ret -1;
    ll r = (s[i + 1] - 1 - a[j].fi) / t * t + a[j].fi;
    while (r + t < s[i + 1]) r += t;
    while (r >= s[i + 1]) r -= t;
    ret r;
}

ll get(ll l, ll r, ll k, ll p, ll R, ll id) {
    if (dp.find({l, r, k, p, R}) != en(dp)) ret dp[{l, r, k, p, R}];
    ll mn = get(l, r);
    ll c1 = (R >= mn ? (ll) 2e18 : cost(mn, -1) +
                                   (mn == l ? 0ll : get(l, mn, n - 1, mn, R, id)) +
                                   (mn + 1 == r ? 0ll : get(mn + 1, r, k, p, R, id)));
    ll c2;
    if (R >= mn) {
        c2 = cost(mn, getx(mn, id)) +
             (mn == l ? 0ll : get(l, mn, id, mn, R, id)) +
             (mn + 1 == r ? 0ll : get(mn + 1, r, k, p, R, id));
    } else {
        c2 = cost(mn, getx(mn, best(mn, k, p))) +
             (mn == l ? 0ll : get(l, mn, best(mn, k, p), mn, R, id)) +
             (mn + 1 == r ? 0ll : get(mn + 1, r, k, p, f[best(mn, k, p)], best(mn, k, p)));
    }
    ret dp[{l, r, k, p, R}] = min({(ll) 2e18, c1, c2});
}

void solve() {
    cin >> X >> n >> m >> w >> t;
    n += 2;
    for1(i, n - 1) cin >> s[i];
    s[n - 1] = X;
    sort(s, s + n);
    a[0] = {0, (ll) 2e18};
    m++;
    for1(i, m) cin >> a[i];
    sort(a, a + m);
    build();
    if (get(0, m, n - 1, m, (ll) -1e18, -1) == (ll) 2e18) assert(0);
    cout << get(0, m, n - 1, m, (ll) -1e18, -1);
}

Compilation message (stderr)

coach.cpp: In function 'int main(int, char**)':
coach.cpp:292:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  292 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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