Submission #67558551

---

Source Code Expand

// 期待外れでいたいだなんて
// いつから願ってしまった？
// 名も知れぬほうがいいなんて
// いつからか願ってしまった

// ココロもネジ巻出して
// 意味を失ってしまった
// 何ひとつも動かせない今日と
// 押しつぶすように広がる

// 澄んだ機械仕掛けの空

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

// Pragmas
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// Namespaces
using namespace std;
using namespace __gnu_pbds;

// Data types
using si  = short int;
using ll  = long long;
using ull = unsigned long long;
using lll = __int128;
using ld  = long double;

// Pairs
using pii  = pair<int, int>;
using psi  = pair<si, si>;
using pll  = pair<ll, ll>;
using plll = pair<lll, lll>;
using pld  = pair<ld, ld>;
#define fi first
#define se second

// PBDS
template<typename Z>
using ordered_set = tree<Z, null_type, less<Z>, rb_tree_tag, tree_order_statistics_node_update>;

// Various outputs and debug
template<typename Z, typename = void> struct is_iterable : false_type {};
template<typename Z> struct is_iterable<Z, void_t<decltype(begin(declval<Z>())),decltype(end(declval<Z>()))>> : true_type {};
template<typename Z> typename enable_if<is_iterable<Z>::value&&!is_same<Z, string>::value,ostream&>::type operator<<(ostream &os, const Z &v);

template<typename Y, typename Z> ostream& operator<<(ostream &os, const pair<Y, Z> &p) {
    return os << "(" << p.fi << ", " << p.se << ")";
}
template<class TupType, size_t... I> void printTuple(ostream& os, const TupType& _tup, index_sequence<I...>) {
    os << "(";
    (..., (os << (I == 0? "" : ", ") << get<I>(_tup)));
    os << ")";
}
template<class... Z> ostream& operator<<(ostream& os, const tuple<Z...>& _tup) {
    printTuple(os, _tup, make_index_sequence<sizeof...(Z)>());
    return os;
}
template<typename Z> typename enable_if<is_iterable<Z>::value&&!is_same<Z, string>::value,ostream&>::type operator<<(ostream &os, const Z &v) {
    os << "["; 
    for (auto it = v.begin(); it != v.end();) { os << *it; if (++it != v.end()) os << ", "; }
    return os << "]";
}

#define debug(...)    logger(cout, #__VA_ARGS__, __VA_ARGS__)
#define debugV(v, x)  vlogger(cout, #v, x, v[x]);
#define rrebug(...)   logger(cerr, #__VA_ARGS__, __VA_ARGS__)
#define rrebugV(v, x) vlogger(cerr, #v, x, v[x]);
template <typename... Args>
void logger(ostream& os, string vars, Args &&...values) {
    os << vars << " = "; string delim = "";
    (..., (os << delim << values, delim = ", "));
    os << "\n";
}
template<class Y, class Z>
void vlogger(ostream& os, string var, Y idx, Z val) {
    os << var << "[" << idx << "] = " << val << "\n";
}

// Various macros
#define All(x)            x.begin(), x.end()
#define Sort(x)           sort(All(x))
#define Reverse(x)        reverse(All(x))
#define Uniqueify(x)      Sort(x); x.erase(unique(All(x)), x.end())
#define RandomSeed        chrono::steady_clock::now().time_since_epoch().count()
#define MultipleTestcases int _tc; cin >> _tc; for (int _cur_tc = 1; _cur_tc <= _tc; _cur_tc++)

// Chmin & chmax
template<typename Z> bool chmin(Z &a, Z b) { return (b < a) ? a = b, true : false; }
template<typename Z> bool chmax(Z &a, Z b) { return (b > a) ? a = b, true : false; }
 
// Modular arithmetic
template<int MOD>
class ModInt {
  public:
    int v;
    ModInt() : v(0) {}
    ModInt(long long _v) {
        v = int((-MOD < _v && _v < MOD) ? (_v) : (_v % MOD));
        if (v < 0) v += MOD;
    }
 
    friend bool operator==(const ModInt &a, const ModInt &b) { return a.v == b.v; }
    friend bool operator!=(const ModInt &a, const ModInt &b) { return a.v != b.v; }
    friend bool operator< (const ModInt &a, const ModInt &b) { return a.v <  b.v; }
    friend bool operator<=(const ModInt &a, const ModInt &b) { return a.v <= b.v; }
    friend bool operator> (const ModInt &a, const ModInt &b) { return a.v >  b.v; }
    friend bool operator>=(const ModInt &a, const ModInt &b) { return a.v >= b.v; }
 
    ModInt &operator+=(const ModInt &a) { v = (long long)(v + a.v) % MOD; return *this; }
    ModInt &operator-=(const ModInt &a) { v = (long long)(v - a.v + MOD) % MOD; return *this; }
    ModInt &operator*=(const ModInt &a) { v = 1ll * v * a.v % MOD; return *this; }
    ModInt &operator/=(const ModInt &a) { return (*this) *= inverse(a); }
 
    friend ModInt pow(ModInt a, long long x) {
        ModInt res = 1;
        for (; x; x /= 2, a *= a) if (x & 1) res *= a;
        return res;
    }
    friend ModInt inverse(ModInt a) { return pow(a, MOD - 2); }
 
    ModInt operator+ () const { return ModInt( v); }
    ModInt operator- () const { return ModInt(-v); }
    ModInt operator++() const { return *this += 1; }
    ModInt operator--() const { return *this -= 1; }
 
    friend ModInt operator+(ModInt a, const ModInt &b) { return a += b; }
    friend ModInt operator-(ModInt a, const ModInt &b) { return a -= b; }
    friend ModInt operator*(ModInt a, const ModInt &b) { return a *= b; }
    friend ModInt operator/(ModInt a, const ModInt &b) { return a /= b; }
 
    friend istream &operator>>(istream &is, ModInt &v) { return is >> v.v; }
    friend ostream &operator<<(ostream &os, const ModInt &v) { return os << v.v; }
};
const int ModA = 998244353;
const int ModC = 1e9 + 7;
using MintA    = ModInt<ModA>;
using MintC    = ModInt<ModC>;

// Other constants
const ll INF  = 1e18;
const ll iINF = 1e9;
const ld EPS  = 1e-9;
const ld iEPS = 1e-6;

const int MX = (1 << 18) + 1;

const int RIGHT_UP   = 0;
const int RIGHT_DOWN = 1;
const int LEFT_DOWN  = 2;
const int LEFT_UP    = 3;
const int END        = 4;
const int LINES      = 5;

int n, m;
ll x[MX];
vector<pair<pii, ll>> adj[6][MX];
bool vis[6][MX];
ll dist[6][MX];

#define m  ((l+r)>>1)
#define lc (pos<<1)
#define rc (lc|1)

void addEdge(int dt, int dv, int ut, int uv, ll w, bool is_up) {
    if (is_up) {
        adj[dt][dv].push_back({{ut, uv}, w});
    } else {
        adj[ut][uv].push_back({{dt, dv}, w});
    }
}

void constructTree(int t, int pos, int l, int r, bool is_right, bool is_up) {
    // debug(t, pos, l, r, is_right, is_up);
    if (l == r) {
        if (is_up) {
            adj[END][l].push_back({{t, pos}, 0});
        } else {
            adj[t][pos].push_back({{END, l}, 0});
        }
        return;
    }

    if (is_up) {
        if (is_right) {
            adj[t][lc].push_back({{t, pos}, x[r] - x[m]});
            adj[t][rc].push_back({{t, pos}, 0});
        } else {
            adj[t][lc].push_back({{t, pos}, 0});
            adj[t][rc].push_back({{t, pos}, x[m+1] - x[l]});
        }
    } else {
        if (is_right) {
            adj[t][pos].push_back({{t, lc}, x[m+1] - x[l]});
            adj[t][pos].push_back({{t, rc}, 0});
        } else {
            adj[t][pos].push_back({{t, lc}, x[r] - x[m]});
            adj[t][pos].push_back({{t, rc}, 0});
        }
    }

    constructTree(t, lc, l, m, is_right, is_up);
    constructTree(t, rc, m+1, r, is_right, is_up);
}

void addLine(int t, int pos, int l, int r, int tl, int tr, int line_id, bool towards_line, bool is_right, ll add = 0) {
    if (tl <= l && r <= tr) {
        // debug(tl, l, r, tr, add);
        if (towards_line) {
            if (is_right) {
                adj[t][pos].push_back({{LINES, line_id}, x[tr] - x[r] + add});
            } else {
                adj[t][pos].push_back({{LINES, line_id}, x[l] - x[tl] + add});
            }
        } else {
            if (is_right) {
                adj[LINES][line_id].push_back({{t, pos}, x[l] - x[tl] + add});
            } else {
                adj[LINES][line_id].push_back({{t, pos}, x[tr] - x[r] + add});
            }
        }
        return;
    }

    if (l != r) {
        addLine(t, lc, l, m, tl, tr, line_id, towards_line, is_right, add);
        addLine(t, rc, m+1, r, tl, tr, line_id, towards_line, is_right, add);
    }
}

#undef m
#undef lc
#undef rc

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> x[i];

    // construct trees
    constructTree(RIGHT_UP, 1, 1, n, true, true);
    constructTree(RIGHT_DOWN, 1, 1, n, true, false);
    constructTree(LEFT_UP, 1, 1, n, false, true);
    constructTree(LEFT_DOWN, 1, 1, n, false, false);

    for (int i = 1; i <= m; i++) {
        int l, r, L, R;
        ll c;
        cin >> l >> r >> L >> R >> c;
        // debug(c);
        if (L > r) {
            addLine(RIGHT_UP, 1, 1, n, l, r, i, true, true, c);
            addLine(RIGHT_DOWN, 1, 1, n, L, R, i, false, true, x[L] - x[r]);
        } else {
            addLine(LEFT_UP, 1, 1, n, l, r, i, true, false, c);
            addLine(LEFT_DOWN, 1, 1, n, L, R, i, false, false, x[l] - x[R]);
        }
    }

    // for (int i = 0; i < 6; i++) {
    //     for (int j = 1; j <= 13; j++) {
    //         cout << "\n";
    //         debug(i, j);
    //         for (auto [np, nw] : adj[i][j]) {
    //             debug(np.fi, np.se, nw);
    //         }
    //     }
    // }

    // dijkstra
    using State = tuple<ll, int, int>;

    for (int t = 0; t < 6; t++) {
        for (int i = 0; i < MX; i++) {
            dist[t][i] = INF;
            vis[t][i] = false;
        }
    }

    priority_queue<State, vector<State>, greater<State>> pyqe;

    dist[END][1] = 0;
    pyqe.push({0, END, 1});
    while (!pyqe.empty()) {
        auto [cd, ct, cv] = pyqe.top(); pyqe.pop();
        if (vis[ct][cv]) continue;

        // debug(cd, ct, cv);

        vis[ct][cv] = true;
        for (auto [np, w] : adj[ct][cv]) {
            auto [nt, nv] = np;
            if (dist[nt][nv] > dist[ct][cv] + w) {
                dist[nt][nv] = dist[ct][cv] + w;
                // debug(cd, ct, nt, dist[nt][nv]);
                pyqe.push({dist[nt][nv], nt, nv});
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (dist[END][i] >= INF) dist[END][i] = -1;
        cout << dist[END][i] << " \n"[i == n];
    }
}

// dibisakan

Submission Info

Judge Result