Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- --┬-- | | --┬-- | |
- | |\ | | | |
- | | \ | | -----> | |
- | | \ | | | |
- | | \ | | | |
- --┴-- | \| | └---- └----
- */
- #define pragma
- #ifdef pragma
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("no-stack-protector")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #pragma GCC optimize("unroll-loops")
- #endif // pragma
- #include<bits/stdc++.h>
- #include<string>
- #define ll long long
- #define all(x) begin(x),end(x)
- #define pb push_back
- #define x first
- #define y second
- #define INF 9223372036854775807ll
- #define PI 3.14159265359d
- #define INPUT "input.txt"
- #define OUTPUT "output.txt"
- #define sz size
- #define rsz resize
- #define int long long
- using namespace std;
- typedef vector<int> vi;
- typedef vector<bool> vb;
- typedef pair<int,int> pii;
- typedef long double ld;
- typedef vector<vi> matrix;
- void seriy() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- #ifdef _android
- freopen("input", "r", stdin);
- freopen("output", "w", stdout);
- #else
- //_android
- #endif
- }
- struct node {
- int val, df;
- };
- node t[10000000 * 8];
- void push(int v) {
- t[v].val += t[v].df;
- t[v * 2 + 1].df += t[v].df;
- t[v * 2 + 2].df += t[v].df;
- t[v].df = 0;
- }
- void update(int v, int l, int r, int tl, int tr, int val) {
- //cerr << tl << " " << tr << " " << l << " " << r << endl;
- push(v);
- if(tl > r || tr < l) {
- return;
- }
- if(tl >= l && tr <= r) {
- t[v].df += val;
- push(v);
- return;
- }
- int tm = (tl + tr) >> 1;
- update(v * 2 + 1, l, r, tl, tm, val);
- update(v * 2 + 2, l, r, tm + 1, tr, val);
- t[v].val = max(t[v * 2 + 1].val, t[v * 2 + 2].val);
- }
- int getmax(int v, int l, int r, int tl, int tr) {
- push(v);
- if(tl > r || tr < l) {
- return -1;
- }
- if(tl >= l && tr <= r) {
- return t[v].val;
- }
- int tm = (tl + tr) >> 1;
- int x = getmax(v * 2 + 1, l, r, tl, tm);
- int y = getmax(v * 2 + 2, l, r, tm + 1, tr);
- return max(x, y);
- }
- signed main(){
- seriy();
- int n, m;
- cin >> n >> m;
- for(int i = 0; i < m; i++) {
- int l, r, val;
- cin >> l >> r >> val;
- l--, r--;
- update(0, l, r, 0, n - 1, val);
- }
- cout << getmax(0, 0, n - 1, 0, n - 1);
- // cout << endl;
- // for(auto i : t) cout << i.val << " ";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement