落谷1607
# include <bits/stdc++.h>
using namespace std; # define ls u<< 1
# define rs u<< 1 | 1 const int N = 1e5 ; int n, k, c, ans;
struct line
{ int l, r, m; bool operator < ( line b) { return r < b. r; }
} s[ N] ; struct tree
{ int l, r, mx, lazy;
} t[ N* 4 ] ; void pushup ( int u) { t[ u] . mx = max ( t[ ls] . mx, t[ rs] . mx) ;
} void pushdown ( int u) { if ( t[ u] . lazy) { t[ ls] . mx += t[ u] . lazy; t[ rs] . mx += t[ u] . lazy; t[ ls] . lazy += t[ u] . lazy; t[ rs] . lazy += t[ u] . lazy; t[ u] . lazy = 0 ; }
} void build ( int u, int l, int r) { t[ u] = { l, r } ; if ( l == r) return ; int mid = l + r >> 1 ; build ( ls, l, mid) ; build ( rs, mid + 1 , r) ; pushup ( u) ;
} void change ( int u, int l, int r, int v) { if ( l > t[ u] . r || r < t[ u] . l) return ; if ( l <= t[ u] . l && r >= t[ u] . r) { t[ u] . mx += v; t[ u] . lazy += v; return ; } pushdown ( u) ; change ( ls, l, r, v) ; change ( rs, l, r, v) ; pushup ( u) ;
} int query ( int u, int l, int r) { if ( l > t[ u] . r || r < t[ u] . l) return 0 ; if ( l <= t[ u] . l && r >= t[ u] . r) { return t[ u] . mx; } pushdown ( u) ; return max ( query ( ls, l, r) , query ( rs, l, r) ) ;
} int main ( ) { cin >> k >> n >> c; for ( int i = 1 ; i <= k; i++ ) { cin >> s[ i] . l >> s[ i] . r >> s[ i] . m; } sort ( s + 1 , s + k + 1 ) ; build ( 1 , 1 , n) ; for ( int i = 1 ; i <= k; i++ ) { int l = s[ i] . l, r = s[ i] . r; int mx = query ( 1 , l, r - 1 ) ; int x = min ( c - mx, s[ i] . m) ; change ( 1 , l, r - 1 , x) ; ans += x; } cout << ans; return 0 ;
}