Submission #4314272

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
template<class V, int NV> struct LazySegTreeWithTwoLazy { // [L,R)
    vector<V> dat; vector<pair<V, V>> lazy; LazySegTreeWithTwoLazy() {
        dat.resize(NV * 2, def); lazy.resize(NV * 2, ldef);
    }
    void update(int a, int b, pair<V, V> v, int k, int l, int r) {
        push(k, l, r); if (r <= a || b <= l) return;
        if (a <= l && r <= b) { setLazy(k, v); push(k, l, r); }
        else {
            update(a, b, v, k * 2 + 1, l, (l + r) / 2); update(a, b, v, k * 2 + 2, (l + r) / 2, r);
            dat[k] = comp(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }
    V get(int a, int b, int k, int l, int r) {
        push(k, l, r); if (r <= a || b <= l) return def;
        if (a <= l && r <= b) return dat[k]; auto x = get(a, b, k * 2 + 1, l, (l + r) / 2);
        auto y = get(a, b, k * 2 + 2, (l + r) / 2, r); return comp(x, y);
    }
    void update(int a, int b, pair<V, V> v) { update(a, b, v, 0, 0, NV); }
    V get(int a, int b) { return get(a, b, 0, 0, NV); }
    // ---- Template ---------------------------------------------------------------------------------
    

    // 区間add, 区間代入, 区間総和
    const V def = 0;
    const pair<V, V> ldef = make_pair(0, -1);
    V comp(V l, V r) { return l + r; }
    void setLazy(int i, pair<V, V> v) { // v = {add, assign}
        if (v.second < 0) {
            lazy[i].first += v.first;
        }
        else {
            lazy[i].first = 0;
            lazy[i].second = v.first + v.second;
        }
    }
    void push(int k, int l, int r) {
        if (0 <= lazy[k].second) dat[k] = lazy[k].second * (r - l);
        dat[k] += lazy[k].first * (r - l);
        if (r - l > 1) { setLazy(k * 2 + 1, lazy[k]); setLazy(k * 2 + 2, lazy[k]); }
        lazy[k] = ldef;
    }
};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/






int N, M;
LazySegTreeWithTwoLazy<ll, 1 << 18> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;

    int t = 0;
    ll ans = 0;
    rep(m, 0, M) {
        int T, L, R;
        cin >> T >> L >> R;
        L--;

        st.update(0, N, { T - t, -1 });
        ans += st.get(L, R);
        st.update(L, R, { 0, 0 });
        t = T;
    }
    cout << ans << endl;
}

Submission Info

Judge Result