Source Code
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, int> pll;

const ll INF = 1e18;
const ll INF2 = 1e15;

const int N = 100100;

struct Segment {
    ll value, offset;
    int i;

    Segment(ll value = INF, ll offset = INF, int i = -1) : value(value), offset(offset), i(i) {
    }

    bool operator<(const Segment& other) const {
        return value + offset < other.value + other.offset;
    }
};

struct SegmentTreeLazy {
#define Mid ((L + R) >> 1)
#define Left (Node << 1)
#define Right (Node << 1 | 1)

   private:
    const ll E = INF;              /// identity element            /// Check this
    const ll EL = INF;             /// identity element for lazy   /// Check this
    static const int Nax = 4 * N;  /// Check this

    int n;  /// Array length
    Segment Tree[Nax];
    ll Lazy[Nax];

   public:
    SegmentTreeLazy(int n = 0) : n(n) {
        for (int Node = 0; Node < Nax; Node++)
            Tree[Node] = Segment(), Lazy[Node] = EL;
    }

   private:
    Segment Unite(Segment x, Segment y) {  /// Check this
        return min(x, y);
    }

   private:
    void Merge(int Node) {
        Tree[Node] = Unite(Tree[Left], Tree[Right]);
    }

   private:
    void PushLazy(int Node, int Len) {
        if (Lazy[Node] != EL) {
            Tree[Node].value = min(Tree[Node].value, Lazy[Node]);  /// Check this
            if (Len > 1) {
                Lazy[Left] = min(Lazy[Left], Lazy[Node]);    /// Check this
                Lazy[Right] = min(Lazy[Right], Lazy[Node]);  /// Check this
            }
            Lazy[Node] = EL;
        }
    }

   public:
    void Build(const vector<ll>& a) {
        Clear();
        n = a.size();
        Build(a, 1, 0, n - 1);
    }

   private:
    void Build(const vector<ll>& a, int Node, int L, int R) {
        Tree[Node] = Segment(), Lazy[Node] = EL;
        if (L == R)
            return void(Tree[Node] = Segment(INF, a[L], L));
        Build(a, Left, L, Mid);
        Build(a, Right, Mid + 1, R);
        Merge(Node);
    }

   public:
    void Update(int i, int j, ll x) {
        if (i < 0)
            i = 0;
        if (j >= n)
            j = n - 1;
        if (n <= 0 || i > j)
            return;
        Update(i, j, x, 1, 0, n - 1);
    }

   private:
    void Update(int i, int j, ll x, int Node, int L, int R) {
        PushLazy(Node, R - L + 1);
        if (j < L || R < i)
            return;
        if (i <= L && R <= j)
            return Lazy[Node] = x, PushLazy(Node, R - L + 1);
        Update(i, j, x, Left, L, Mid);
        Update(i, j, x, Right, Mid + 1, R);
        Merge(Node);
    }

   public:
    Segment Query(int i, int j) {
        if (i < 0)
            i = 0;
        if (j >= n)
            j = n - 1;
        if (n <= 0 || i > j)
            return Segment();
        return Query(i, j, 1, 0, n - 1);
    }

   private:
    Segment Query(int i, int j, int Node, int L, int R) {
        PushLazy(Node, R - L + 1);
        if (j < L || R < i)
            return Segment();
        if (i <= L && R <= j)
            return Tree[Node];
        return Unite(Query(i, j, Left, L, Mid), Query(i, j, Right, Mid + 1, R));
    }

   public:
    void Destroy(int i) {
        if (i < 0 || i >= n) {
            return;
        }
        return Destroy(i, 1, 0, n - 1);
    }

    void Destroy(int i, int Node, int L, int R) {
        PushLazy(Node, R - L + 1);
        if (L == R) {
            return void(Tree[Node].offset = INF);
        }
        if (i <= Mid) {
            Destroy(i, Left, L, Mid);
        } else {
            Destroy(i, Right, Mid + 1, R);
        }
        Merge(Node);
    }

   private:
    void Clear() {
        for (int Node = 0; Node <= 4 * n; Node++)
            Tree[Node] = Segment(), Lazy[Node] = EL;
        n = 0;
    }

#undef Mid
#undef Left
#undef Right
};

SegmentTreeLazy myTree1;
SegmentTreeLazy myTree2;

int main() {
    int n, q;
    cin >> n >> q;

    vector<ll> a(n);
    for (ll& x : a) {
        scanf("%lld", &x);
    }

    vector<vector<int>> b(n), c(n);

    while (q--) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        x--, y--, z--;
        b[x].push_back(y);
        c[x].push_back(z);
    }

    myTree1.Build(a);
    myTree1.Update(0, 0, -a[0]);

    vector<ll> neg_a = a;
    for (ll& x : neg_a) {
        x = -x;
    }

    myTree2.Build(neg_a);
    myTree2.Update(0, 0, -neg_a[0]);

    vector<ll> answer(n, -1);

    while (true) {
        Segment s1 = myTree1.Query(0, n - 1);
        Segment s2 = myTree2.Query(0, n - 1);

        if (s1 < s2) {
            swap(s1, s2);
        }

        if (min(s1.value + s1.offset, s2.value + s2.offset) > INF2) {
            break;
        }

        int i = -1;

        if (s1 < s2) {
            i = s1.i;
            answer[i] = s1.value + s1.offset;
        } else {
            i = s2.i;
            answer[i] = s2.value + s2.offset;
        }

        for (int j = 0; j < b[i].size(); j++) {
            myTree1.Update(max(i + 1, b[i][j]), c[i][j], answer[i] - a[i]);
            myTree2.Update(b[i][j], min(i - 1, c[i][j]), answer[i] + a[i]);
        }

        myTree1.Destroy(i);
        myTree2.Destroy(i);
    }

    answer[0] = 0;
    for (int i = 0; i < n; i++) {
        printf("%lld%c", answer[i], " \n"[i + 1 == n]);
    }
}
Copy
Fallout: New Vegas Baraa_Armoush
GNU G++17
14 ms
25.5 MB
Wrong Answer
Test Case #1
14 ms
25.3 MB
Accepted
Input
6 3
1 2 3 4 5 6
1 3 3
2 1 4
3 2 2
Output
0 3 2 5 -1 -1
Judge Output
0 3 2 5 -1 -1
Checker Message
6 numbers
Test Case #2
14 ms
25.5 MB
Wrong Answer
Input
18 16
1 4 5 6 8 9 10 13 14 16 20 21 23 24 25 26 27 29
2 2 5
10 18 18
1 1 17
3 10 14
4 3 6
16 9 11
2 1 4
7 10 11
3 2 2
6 2 3
2 14 18
4 10 14
3 5 6
2 16 18
3 13 15
5 1 1
Output
0 3 4 5 7 8 9 12 37 15 31 20 22 23 24 25 26 28
Judge Output
0 3 4 5 7 8 9 12 13 15 19 20 22 23 24 25 26 28
Checker Message
9th numbers differ - expected: '13', found: '37'