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 EL = INF;             /// identity element for lazy   /// Check this
    static const int Nax = 4 * N;  /// Check this

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

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

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

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

   private:
    void PushLazy(int Node, int Len) {
        if (Lazy[Node] != EL) {
            if (Tree1[Node].value + Tree1[Node].offset > Lazy[Node] + Tree2[Node].offset) {
                Tree1[Node].value = Lazy[Node];
                Tree1[Node].offset = Tree2[Node].offset;
                Tree1[Node].i = Tree2[Node].i;
            }
            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) {
        Tree1[Node] = Segment();
        Tree2[Node] = Segment(0);
        Lazy[Node] = EL;
        if (L == R) {
            Tree1[Node] = Segment(INF, a[L], L);
            Tree2[Node] = Segment(0, a[L], L);
            return;
        }
        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 Tree1[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);
    }

   private:
    void Destroy(int i, int Node, int L, int R) {
        PushLazy(Node, R - L + 1);
        if (i < L || R < i) {
            return;
        }
        if (L == R) {
            return void(Tree1[Node].offset = Tree2[Node].offset = INF);
        }

        Destroy(i, Left, L, Mid);
        Destroy(i, Right, Mid + 1, R);
        Merge(Node);
    }

   private:
    void Clear() {
        for (int Node = 0; Node <= 4 * n; Node++)
            Tree1[Node] = Segment(), Tree2[Node] = Segment(0), 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 (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
240 ms
59.1 MB
Accepted