Submission #4302281

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>
#include <numeric>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

template<typename T> class segtree {
private:
    int n,sz,h; vector<T> node, lazy_update, lazy_add; vector<bool> lazyFlag;
public:
    segtree(vector<T> v) : n(1), sz((int)v.size()), h(0){
        while(n < sz) n *= 2, h++;
        node.resize(2*n, 0);
        lazy_update.resize(2*n, 0); lazyFlag.resize(2*n,false);
        lazy_add.resize(2*n, 0);
        for(int i = 0; i < sz; i++) node[i+n] = v[i];
        for(int i=n-1; i>=1; i--) node[i] = node[2*i] + node[2*i+1];
    }
    void eval(int k) {
        if(lazyFlag[k]){
            lazy_update[k] += lazy_add[k];
            node[k] = lazy_update[k];
            if(k < n) {
                lazy_add[2*k] = lazy_add[2*k+1] = 0;
                lazy_update[2*k] = lazy_update[2*k+1] = lazy_update[k] / 2;
                lazyFlag[2*k] = lazyFlag[2*k+1] = true;
            }
            lazy_add[k] = 0;
            lazyFlag[k] = false;
        }else if(lazy_add[k] != 0){
            node[k] += lazy_add[k];
            if(k < n){
                lazy_add[2*k] += lazy_add[k] / 2; lazy_add[2*k+1] += lazy_add[k] / 2;
            }
            lazy_add[k] = 0;
        }
    }
    void update(int a, int b, T x, int k=1, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b){
            lazy_add[k] = 0; lazy_update[k] = x*(r-l); lazyFlag[k] = true; eval(k);
        }else{
            update(a, b, x, 2*k, l, (l+r)/2); update(a, b, x, 2*k+1, (l+r)/2, r);
            node[k] = node[2*k] + node[2*k+1];
        }
    }
    void add(int a, int b, T x, int k=1, int l=0, int r=-1){
        if(r < 0) r = n;
        eval(k);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b){
            lazy_add[k] += x*(r-l); eval(k);
        }else{
            add(a, b, x, 2*k, l, (l+r)/2); add(a, b, x, 2*k+1, (l+r)/2, r);
            node[k] = node[2*k] + node[2*k+1];
        }
    }
    T query(int a, int b) {
        a += n, b += n - 1;
        for(int i = h; i > 0; i--) eval(a >> i), eval(b >> i);
        b++;
        T res1 = 0, res2 = 0;
        while(a < b) {
            if(a & 1) eval(a), res1 += node[a++];
            if(b & 1) eval(--b), res2 += node[b];
            a >>= 1, b >>= 1;
        }
        return res1 + res2;
    }
    void print(){for(int i = 0; i < sz; i++)cout<<query(i,i+1)<< " ";cout<<endl;}
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    ll ans = 0;
    vector<ll>v(n);
    segtree<ll>sg(v);
    ll tt = 0;
    rep(i,m){
        ll t,l,r;
        cin >> t >> l >> r;
        l--;
        r--;
        sg.add(0,n,t-tt);
        tt = t;
        ans += sg.query(l,r+1);
        sg.update(l,r+1,0);
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result