Language: C++

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

//#define TLE

// 1 次元座標圧縮
// 値のバリエーションが 10^7 以下程度なら
// 圧縮して保持することで TLE を防げる
class CoordComp {
    public:
        // 値を追加します O(1)
        // 重複した値は意味がないので、削除します
        void Add(ll v) { m_V.push_back(v); }

        // 値の追加を終え座標を圧縮します O(N log N)
        void Build() {
            sort(m_V.begin(), m_V.end());
            m_V.erase(unique(m_V.begin(), m_V.end()), m_V.end());
            // 圧縮した各値のインデックス * 2 + 1 を圧縮後の値とする
            m_Decomp.assign(m_V.size() * 2 + 1, 0);
            for(int i = 0; i < m_V.size(); ++i) {
                m_Comp[m_V[i]] = i * 2 + 1;
                m_Decomp[i * 2 + 1] = m_V[i];
            }
            // m_Decompress の埋まっていない部分を作成
            assert(m_Decomp.size() >= 3);
            m_Decomp[0] = m_Decomp[1] - 1;
            m_Decomp[m_Decomp.size()-1] = m_Decomp[m_Decomp.size()-2] + 1;
            for(int i = 1; i < m_V.size(); ++i) {
                m_Decomp[i*2] = (m_Decomp[i*2-1] + m_Decomp[i*2+1]) / 2;
            }
        }

        // n の圧縮後の世界での値を返します O(log N)
        ll GetComp(ll n) {
            // あるならそれを返す
            if(m_Comp.count(n) > 0) { return m_Comp[n]; }
            // 最小値より小さい／最大値より大きい処理
            if(n < m_V[0]) { return 0; }
            if(m_V[m_V.size()-1] < n) { return m_V.size() * 2; }
            // そうでないならある 2 点の間
            auto it = upper_bound(m_Decomp.begin(), m_Decomp.end(), n);
            return static_cast<ll>(it - m_Decomp.begin()) - 1;
        }

        // n の圧縮前の世界での値を返します O(1)
        // 一意に特定できない場合、以下の値を返します
        // A) 追加済みの 2 点の間に含まれる値の場合　…　その 2 点の中間の値を返す
        // B) 追加済みのどの点より大きいまたは小さい　…　追加済みの最小点 - 1／最大点 + 1 を返す
        ll GetDecomp(ll n) {
            assert(0 <= n && n < m_Decomp.size());
            return m_Decomp[n];
        }
        // 圧縮前の世界に n があるなら true を返します O(log N)
        bool IsFind(ll n) { return binary_search(m_V.begin(), m_V.end(), n); }
        // 座標圧縮後の空間のサイズです O(1)
        size_t GetSize() { return m_Decomp.size(); }
    private:
        vector<ll> m_V;         // 管理する一次元座標一覧
        map<ll, ll> m_Comp;     // 値を圧縮後の値に
        vector<ll> m_Decomp;    // 圧縮された値を元の値に
};

// 座標圧縮セグメント木
// 座標圧縮する関係上 Build() 後の値更新ができないが、
// 扱える範囲が拡大した。 10^9 程度の範囲なら問題なく扱える
template<typename SType>
class CompSegmentTree {
    public:
        using Func = function< SType(SType, SType) >;
    private:
        class SegmentTreeImpl {
            public:
                SegmentTree() {}
                SegmentTree(ll n, const Func f, const SType &e) { Init(n, f, e); }
                void Init(ll n, const Func f, const SType &e) {
                    m_F = f; m_E = e;
                    m_Size = 1;
                    while(m_Size < n) { m_Size <<= 1; }
                    m_Seg.assign(2 * m_Size, m_E);
                }
                void Update(int k, const SType &x) {
                    k += m_Size;
                    m_Seg[k] = x;
                    while(k >>= 1) {
                        m_Seg[k] = m_F(m_Seg[2 * k + 0], m_Seg[2 * k + 1]);
                    }
                }
                void Build() {
                    for(ll k = m_Size - 1; k > 0; k--) {
                        m_Seg[k] = m_F(m_Seg[2 * k + 0], m_Seg[2 * k + 1]);
                    }
                }
                SType Query(ll a, ll b) {
                    SType l = m_E, r = m_E;
                    for(a += m_Size, b += m_Size; a < b; a >>= 1, b >>= 1) {
                        if(a & 1) l = m_F(l, m_Seg[a++]);
                        if(b & 1) r = m_F(m_Seg[--b], r);
                    }
                    return m_F(l, r);
                }
                SType operator[](const ll &k) const
                {
                    return m_Seg[k + m_Size];
                }
            private:
                Func m_F;
                SType m_E;
                int m_Size;
                vector< SType > m_Seg;
        };

        class CoordCompImpl {
            public:
                void Add(ll v) { m_V.push_back(v); }
                void Build() {
                    sort(m_V.begin(), m_V.end());
                    m_V.erase(unique(m_V.begin(), m_V.end()), m_V.end());
                    m_Decomp.assign(m_V.size() * 2 + 1, 0);
                    for(int i = 0; i < m_V.size(); ++i) {
                        m_Comp[m_V[i]] = i * 2 + 1;
                        m_Decomp[i * 2 + 1] = m_V[i];
                    }
                    assert(m_Decomp.size() >= 3);
                    m_Decomp[0] = m_Decomp[1] - 1;
                    m_Decomp[m_Decomp.size()-1] = m_Decomp[m_Decomp.size()-2] + 1;
                    for(int i = 1; i < m_V.size(); ++i) {
                        m_Decomp[i*2] = (m_Decomp[i*2-1] + m_Decomp[i*2+1]) / 2;
                    }
                }
                ll GetComp(ll n) {
                    if(m_Comp.count(n) > 0) { return m_Comp[n]; }
                    if(n < m_V[0]) { return 0; }
                    if(m_V[m_V.size()-1] < n) { return m_V.size() * 2; }
                    auto it = upper_bound(m_Decomp.begin(), m_Decomp.end(), n);
                    return static_cast<ll>(it - m_Decomp.begin()) - 1;
                }
                size_t GetSize() { return m_Decomp.size(); }
            private:
                vector<ll> m_V;
                map<ll, ll> m_Comp;
                vector<ll> m_Decomp;
        };

    public:

        CompSegmentTree(const Func f, const SType &e) : m_F(f), m_E(e) {}

        // i を n で更新します O(log N)
        void Update(ll i, ll n) {
            if(m_PosVal.count(i) > 0) {
                m_PosVal[i] = m_F(m_PosVal[i], n);
            }
            else { m_PosVal[i] = n; }
            m_Cc.Add(i);
        }
        // セグ木を構築します O(N log N)
        // f: セグ木で判定する関数
        // e: 単位元
        void Build() {
            m_Cc.Build();   // 座標圧縮
            m_SegTree.Init(m_Cc.GetSize(), m_F, m_E);
            for(auto& pv : m_PosVal) {
                ll ind = m_Cc.GetComp(pv.first);    // 座標圧縮後の位置
                ll val = pv.second;                 // 位置に設定された値
                m_SegTree.Update(ind, val);
            }
            m_SegTree.Build();  // セグ木構築
        }

        // 区間 [a, b) に Func f を行った結果を返す O(log log N)
        SType Query(ll a, ll b) {
            return m_SegTree.Query(m_Cc.GetComp(a), m_Cc.GetComp(b));
        }

    private:
        Func m_F;                   // モノイド
        SType m_E;                  // 単位元
        map<ll, ll> m_PosVal;       // i にセットされた値
        SegmentTreeImpl m_SegTree;
        CoordCompImpl m_Cc;
};

class CompLazySegmentTree {
    private:
        class LazySegmentTreeImpl {
            private:
                // 遅延評価の種類を表す enum
                enum Status {
                    None = 0,           // 遅延評価なし
                    Update_Min = 1,     // min の遅延評価
                    Update_Reset = 2    // 更新の遅延評価
                };

            public:
                LazySegmentTree() {}
                LazySegmentTree(ll n) { Init(n); }
                // 初期化
                // n: セグメント木で扱う配列の長さ
                void Init(ll n) {
                    // 要素数を 2 べきにする
                    m_Size = 1;
                    while(m_Size < n) { m_Size <<= 1; }
                    m_Seg.assign(2 * m_Size, LLINF);    // 単位元で初期化
                    m_Lazy.assign(2 * m_Size, LLINF);
                    m_LazyFlag.assign(2 * m_Size, None);
                }
                // k 番目の要素に x をセット (0-indexed)
                void Set(ll k, ll x) {
                    assert(0 <= k && k < m_Size);
                    m_Seg[k + m_Size] = x;
                }
                // セグ木構築 O(N)
                void Build() {
                    for(int k = m_Size - 1; k > 0; k--) {
                        // 子ノードに対しての演算結果を親ノードに格納
                        m_Seg[k] = min(m_Seg[2 * k + 0] , m_Seg[2 * k + 1]);
                    }
                }
                // 区間 [a, b) に対して x との min をとります。 O(log N)
                void Update(ll a, ll b, ll x) {
                    assert(0 <= a && a <= b && b <= m_Size);
                    UpdateImpl(a, b, x, 1, 0, m_Size);
                }
                // 区間 [a, b) 全ての要素を x に置き換えます。 O(log N)
                void Reset(ll a, ll b, ll x) {
                    assert(0 <= a && a <= b && b <= m_Size);
                    ResetImpl(a, b, x, 1, 0, m_Size);
                }
                // 区間 [a, b) の最小値を返します。 O(log N)
                ll Query(ll a, ll b) {
                    assert(0 <= a && a <= b && b <= m_Size);
                    return QueryImpl(a, b, 1, 0, m_Size);
                }
                // セグ木で管理している要素の k 番目にアクセスします O(log N)
                ll operator[](const ll &k) {
                    assert(0 <= k && k < m_Size);
                    return Query(k, k + 1);
                }

            private:
                // セグ木の k 地点から長さ length ぶんの区間遅延評価を行います
                void Propagate(ll k, ll length) {
                    if(m_LazyFlag[k] == Update_Min) {
                        if(k < m_Size) {
                            // 違うタイプのものがまだ伝搬していないなら更に下に伝搬させておく
                            if(m_LazyFlag[2 * k + 0] == Update_Reset) { Propagate(2 * k + 0, length / 2); }
                            if(m_LazyFlag[2 * k + 1] == Update_Reset) { Propagate(2 * k + 1, length / 2); }
                            // 子があるなら子の遅延配列に値を伝搬
                            m_Lazy[2 * k + 0] = min(m_Lazy[2 * k + 0], m_Lazy[k] / 2);
                            m_Lazy[2 * k + 1] = min(m_Lazy[2 * k + 1], m_Lazy[k] / 2);
                            m_LazyFlag[2 * k + 0] = m_LazyFlag[2 * k + 1] = Update_Min;
                        }
                        m_Seg[k] = min(m_Seg[k], m_Lazy[k]);  // 遅延評価ぶんの反映
                        m_Lazy[k] = LLINF;
                        m_LazyFlag[k] = None;
                    }
                    else if(m_LazyFlag[k] == Update_Reset) {
                        if(k < m_Size) {
                            m_Lazy[2 * k + 0] = m_Lazy[2 * k + 1] = m_Lazy[k] / 2;
                            m_LazyFlag[2 * k + 0] = m_LazyFlag[2 * k + 1] = Update_Reset;
                        }
                        m_Seg[k] = m_Lazy[k];
                        m_Lazy[k] = LLINF;
                        m_LazyFlag[k] = None;
                    }
                }
                // 区間 [a, b) に対して x との min をとります O(log N)
                // そのうち m_Seg のインデックス k で管理される区間 [l, r) に対して処理します
                // 0-indexed
                void UpdateImpl(ll a, ll b, ll x, ll k, ll l, ll r) {
                    Propagate(k, r - l);   // 管理範囲を遅延評価
                    if(b <= l || r <= a) { return; }   // 範囲外
                    if(a <= l && r <= b) {
                        // 完全に包含しているなら
                        // 管理している範囲の要素数 * x で min をとればよい
                        m_Lazy[k] = min(m_Lazy[k], (r - l) * x);
                        m_LazyFlag[k] = Update_Min;
                        // その後遅延評価
                        Propagate(k, r - l);
                    }
                    else {
                        // 範囲が中途半端なら再帰
                        UpdateImpl(a, b, x, 2 * k + 0, l, (l + r) >> 1);
                        UpdateImpl(a, b, x, 2 * k + 1, (l + r) >> 1, r);
                        m_Seg[k] = min(m_Seg[2 * k + 0], m_Seg[2 * k + 1]);
                    }
                };
                // 区間 [a, b) 全ての要素を x にします O(log N)
                // そのうち m_Seg のインデックス k で管理される区間 [l, r) に対して処理します
                // 0-indexed
                void ResetImpl(ll a, ll b, ll x, ll k, ll l, ll r) {
                    Propagate(k, r - l);
                    if(b <= l || r <= a) { return; }
                    if(a <= l && r <= b) {
                        m_Lazy[k] = (r - l) * x;
                        m_LazyFlag[k] = Update_Reset;
                        // その後遅延評価
                        Propagate(k, r - l);
                    }
                    else {
                        // 範囲が中途半端なら再帰
                        ResetImpl(a, b, x, 2 * k + 0, l, (l + r) >> 1);
                        ResetImpl(a, b, x, 2 * k + 1, (l + r) >> 1, r);
                        m_Seg[k] = min(m_Seg[2 * k + 0], m_Seg[2 * k + 1]);
                    }
                };
                // 区間 [a,b) の min を返すために、
                // そのうち m_Seg のインデックス k で管理される区間 [l, r) に対して処理します
                // O(log N)
                ll QueryImpl(ll a, ll b, ll k, ll l, ll r) {
                    Propagate(k, r - l);
                    if(b <= l || r <= a) { return LLINF; }
                    if(a <= l && r <= b) { return m_Seg[k]; }
                    return min(QueryImpl(a, b, 2 * k + 0, l, (l + r) >> 1),
                            QueryImpl(a, b, 2 * k + 1, (l + r) >> 1, r));
                }

    private:
        ll m_Size;                  // セグ木の要素数
        vector<ll> m_Seg;           // セグ木本体。一次元で管理
        vector<ll> m_Lazy;          // 遅延評価伝搬配列
        vector<ll> m_LazyFlag;      // どのタイプの遅延評価を行うかのフラグ
};

        class CoordCompImpl {
            public:
                void Add(ll v) { m_V.push_back(v); }
                void Build() {
                    sort(m_V.begin(), m_V.end());
                    m_V.erase(unique(m_V.begin(), m_V.end()), m_V.end());
                    m_Decomp.assign(m_V.size() * 2 + 1, 0);
                    for(int i = 0; i < m_V.size(); ++i) {
                        m_Comp[m_V[i]] = i * 2 + 1;
                        m_Decomp[i * 2 + 1] = m_V[i];
                    }
                    assert(m_Decomp.size() >= 3);
                    m_Decomp[0] = m_Decomp[1] - 1;
                    m_Decomp[m_Decomp.size()-1] = m_Decomp[m_Decomp.size()-2] + 1;
                    for(int i = 1; i < m_V.size(); ++i) {
                        m_Decomp[i*2] = (m_Decomp[i*2-1] + m_Decomp[i*2+1]) / 2;
                    }
                }
                ll GetComp(ll n) {
                    if(m_Comp.count(n) > 0) { return m_Comp[n]; }
                    if(n < m_V[0]) { return 0; }
                    if(m_V[m_V.size()-1] < n) { return m_V.size() * 2; }
                    auto it = upper_bound(m_Decomp.begin(), m_Decomp.end(), n);
                    return static_cast<ll>(it - m_Decomp.begin()) - 1;
                }
                size_t GetSize() { return m_Decomp.size(); }
            private:
                vector<ll> m_V;
                map<ll, ll> m_Comp;
                vector<ll> m_Decomp;
        };

    public:

        // [l, r) を n で更新します O(log N)
        void Update(ll l, ll r, ll n) {
            if(l > r) { swap(l, r); }
            if(m_PosVal.count(make_pair(l, r)) > 0) {
                m_PosVal[make_pair(l, r)] = min(m_PosVal[make_pair(l, r)], n);
            }
            else {
                m_PosVal[make_pair(l, r)] = n;
            }
            m_Cc.Add(l);
            m_Cc.Add(r);
        }
        // セグ木を構築します O(N log N)
        void Build() {
            m_Cc.Build();
            m_SegTree.Init(m_Cc.GetSize());
            for(auto& pv : m_PosVal) {
                ll lb = m_Cc.GetComp(pv.first.first);
                ll rb = m_Cc.GetComp(pv.first.second);
                ll val = pv.second;                 // 位置に設定された値
                m_SegTree.Update(lb, rb, val);
            }
            m_SegTree.Build();  // セグ木構築
        }
        // 区間 [a, b) の最小値を取得します O(log log N)
        ll Query(ll a, ll b) {
            return m_SegTree.Query(m_Cc.GetComp(a), m_Cc.GetComp(b));
        }

    private:
        map< pair<ll, ll>, ll> m_PosVal;    // 範囲 [l, r) にセットされた値
        LazySegmentTreeImpl m_SegTree;
        CoordCompImpl m_Cc;
};

ll N, Q;
vector<ll> S, T, X, D;

signed main()
{
    cin >> N >> Q;
    S.resize(N);
    T.resize(N);
    X.resize(N);
    D.resize(Q);
    REP(i, N) { cin >> S[i] >> T[i] >> X[i]; }
    REP(i, Q) { cin >> D[i]; }

#ifdef TLE
    // 区間 min
    auto Rmq = [](int a, int b) -> int
    {
        return min(a, b);
    };

    CompSegmentTree<ll> cst(Rmq, LLINF);
    REP(i, N) {
        ll lb = S[i] - X[i];
        ll ub = T[i] - X[i];
        for(int j = lb; j < ub; ++j) {
            cst.Update(j, X[i]);
        }
    }
    cst.Build();

    REP(i, Q) {
        ll val = cst.Query(D[i], D[i]+1);
        printf("%lld\n", val == LLINF ? -1 : val);
    }
#else
    CompLazySegmentTree clst;
    REP(i, N) {
        ll lb = S[i] - X[i];
        ll ub = T[i] - X[i];
        clst.Update(lb, ub, X[i]);
    }
    clst.Build();

    REP(i, Q) {
        ll val = clst.Query(D[i], D[i]+1);
        printf("%lld\n", val == LLINF ? -1 : val);
    }
#endif
    return 0;
}


Compiler output:
a.cc:93:17: error: ISO C++ forbids declaration of 'SegmentTree' with no type [-fpermissive]
   93 |                 SegmentTree() {}
      |                 ^~~~~~~~~~~
a.cc:94:17: error: ISO C++ forbids declaration of 'SegmentTree' with no type [-fpermissive]
   94 |                 SegmentTree(ll n, const Func f, const SType &e) { Init(n, f, e); }
      |                 ^~~~~~~~~~~
a.cc: In member function 'int CompSegmentTree<SType>::SegmentTreeImpl::SegmentTree()':
a.cc:93:32: warning: no return statement in function returning non-void [-Wreturn-type]
   93 |                 SegmentTree() {}
      |                                ^
a.cc: In member function 'int CompSegmentTree<SType>::SegmentTreeImpl::SegmentTree(ll, CompSegmentTree<SType>::Func, const SType&)':
a.cc:94:82: warning: no return statement in function returning non-void [-Wreturn-type]
   94 |                 SegmentTree(ll n, const Func f, const SType &e) { Init(n, f, e); }
      |                                                                                  ^
a.cc: At global scope:
a.cc:215:17: error: ISO C++ forbids declaration of 'LazySegmentTree' with no type [-fpermissive]
  215 |                 LazySegmentTree() {}
      |                 ^~~~~~~~~~~~~~~
a.cc:216:17: error: ISO C++ forbids declaration of 'LazySegmentTree' with no type [-fpermissive]
  216 |                 LazySegmentTree(ll n) { Init(n); }
      |                 ^~~~~~~~~~~~~~~
a.cc: In member function 'int CompLazySegmentTree::LazySegmentTreeImpl::LazySegmentTree()':
a.cc:215:36: warning: no return statement in function returning non-void [-Wreturn-type]
  215 |                 LazySegmentTree() {}
      |                                    ^
a.cc: In member function 'int CompLazySegmentTree::LazySegmentTreeImpl::LazySegmentTree(ll)':
a.cc:216:50: warning: no return statement in function returning non-void [-Wreturn-type]
  216 |                 LazySegmentTree(ll n) { Init(n); }
      |                                                  ^