fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define sz(a) (int)a.size()
  6. #define mask(i) ((1LL) << (i))
  7. #define bit(x, i) ((x) >> (i) & (1LL))
  8. #define all(x) (x).begin(),(x).end()
  9. #define debug(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ << "] = [" ,DBG(__VA_ARGS__)
  10.  
  11. string to_string(const string& s) { return '"' + s + '"'; }
  12. void DBG() { cerr << "]" << endl; }
  13. template<class H, class... T> void DBG(H h, T... t) {
  14.     cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...);
  15. }
  16.  
  17. template <class T> 
  18. inline bool minimize(T &a, const T &b) { return (a > b ? (a = b, 1) : 0); }
  19. template <class T> 
  20. inline bool maximize(T &a, const T &b) { return (a < b ? (a = b, 1) : 0); }
  21.  
  22. void file() {
  23.     #define TASK "TASK"
  24.     // freopen(TASK".inp", "r", stdin);
  25.     // freopen(TASK".out", "w", stdout);
  26. }
  27.  
  28. const int INF = 3e18 + 5062007;
  29. const int mod = 1e9 + 7;
  30. const int nmax = 2e5 + 5;
  31.  
  32. struct info {
  33.     int a, b, c;
  34. };
  35.  
  36. int n, dp[nmax];
  37. info a[nmax];
  38. vector <int> d;
  39.  
  40. template <class T = int> struct Segtree {
  41.     T st[nmax << 2], lz[nmax << 2];
  42.     void pushUp(int id) {
  43.         st[id] = max(st[id * 2], st[id * 2 + 1]);
  44.     }
  45.  
  46.     void update(int id, int l, int r, int pos, T val) {
  47.         if (pos < l || pos > r) return;
  48.         if (l == r) {
  49.             st[id] = max(st[id], val);
  50.             return;
  51.         }
  52.         int mid = l + r >> 1;
  53.         update(id * 2, l, mid, pos, val);
  54.         update(id * 2 + 1, mid + 1, r, pos, val);
  55.         pushUp(id);
  56.     }
  57.     void add(int u, int v) {
  58.         st[u] += lz[v];
  59.         lz[u] += lz[v];
  60.     }
  61.     void pushDown(int id) {
  62.         add(id, id * 2);
  63.         add(id, id * 2 + 1);
  64.         lz[id] = 0;
  65.     }
  66.     void update(int id, int l, int r, int u, int v, T val) {
  67.         if (v < l || u > r) return;
  68.         if (u <= l && v >= r) {
  69.             return;
  70.         }
  71.         int mid = l + r >> 1;
  72.         update(id * 2, l, mid, u, v, val);
  73.         update(id * 2 + 1, mid + 1, r, u, v, val);
  74.         pushUp(id);
  75.     }
  76.     T query(int id, int l, int r, int u, int v) {
  77.         if (v < l || u > r) return 0;
  78.         if (u <= l && v >= r) return st[id];
  79.         int mid = l + r >> 1;
  80.         T L = query(id * 2, l, mid, u, v);
  81.         T R = query(id * 2 + 1, mid + 1, r, u, v);
  82.         return max(L, R);
  83.     }
  84. };
  85. Segtree A;
  86.  
  87. void solve() {
  88.     cin >> n;
  89.     for (int i = 1; i <= n; ++i) {
  90.         cin >> a[i].a >> a[i].b >> a[i].c;
  91.         d.emplace_back(a[i].a);
  92.         d.emplace_back(a[i].b);
  93.     }
  94.  
  95.     sort(all(d));
  96.  
  97.     for (int i = 1; i <= n; ++i) {
  98.         a[i].a = lower_bound(all(d), a[i].a) - d.begin();
  99.         a[i].b = lower_bound(all(d), a[i].b) - d.begin();
  100.         a[i].a++, a[i].b++;
  101.     }
  102.  
  103.     sort(a + 1, a + 1 + n, [](const info &x, const info &y) {
  104.         return x.a < y.a || (x.a == y.a && x.b < y.b);
  105.     });
  106.  
  107.     for (int i = 1; i <= n; ++i) {
  108.         dp[i] = a[i].c;
  109.         dp[i] = max(dp[i], A.query(1, 1, 2 * n, 1, a[i].a) + a[i].c);
  110.         A.update(1, 1, 2 * n, a[i].b, dp[i]);
  111.     }    
  112.  
  113.     int ans = 0;
  114.     for (int i = 1; i <= n; ++i) 
  115.         ans = max(ans, dp[i]);
  116.     cout << ans;
  117. }
  118.  
  119. signed main() {
  120.     ios_base::sync_with_stdio(false);
  121.     cin.tie(nullptr);cout.tie(nullptr);
  122.     file();
  123.     int tt = 1;
  124.     // cin >> tt;
  125.  
  126.     // process();
  127.     while(tt--)  {
  128.         solve();
  129.         // brute();
  130.     }
  131.     cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  132.     return 0;
  133. }
  134. //567
  135.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kbfPwM
language:
C++14 (gcc 8.3)
created:
44 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!