Guest User

Untitled

a guest
Oct 13th, 2019
302
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. struct vertex
  7. {
  8.     int in, out, cost;
  9. };
  10.  
  11. using heap = priority_queue<ll>;
  12.  
  13. void combine (heap *to_ptr, heap *what_ptr) {
  14.     heap &to = *to_ptr;
  15.     heap &what = *what_ptr;
  16.  
  17.     if (to.size() < what.size())
  18.         swap(to, what);
  19.  
  20.     vector<ll> to_push;
  21.     while (!what.empty())
  22.     {
  23.         ll x = what.top();
  24.         ll y = to.top();
  25.         what.pop(); to.pop();
  26.         to_push.push_back(x + y);
  27.     }
  28.  
  29.     for (ll x : to_push)
  30.         to.push(x);
  31.     delete what_ptr;
  32. }
  33.  
  34. bool in (const vertex &inner, const vertex &outer)
  35. {
  36.     return outer.in <= inner.in && inner.out <= outer.out;
  37. }
  38.  
  39. heap* dfs (int v, int &ptr, const vector<vertex> &vs)
  40. {
  41.     heap* ans = new heap();
  42.  
  43.     while (ptr < int(vs.size()) && in(vs[ptr], vs[v]))
  44.     {
  45.         ptr++;
  46.         auto son = dfs(ptr - 1, ptr, vs);
  47.         combine(ans, son);
  48.     }
  49.  
  50.     ans->push(vs[v].cost);
  51.     return ans;
  52. }
  53.  
  54. void solve(istream &cin = std::cin, ostream &cout = std::cout) {
  55.  
  56.     auto solve_test = [&]
  57.     {
  58.         int n;
  59.         if (!(cin >> n))
  60.             return false;
  61.  
  62.         const int bnd = int(1e6) + 1;
  63.  
  64.         vector<vertex> vs(n);
  65.         for (auto &p : vs)
  66.             cin >> p.in >> p.out >> p.cost;
  67.  
  68.         vs.push_back(vertex{0, bnd, 0});
  69.  
  70.         sort(vs.begin(), vs.end(), [&] (const vertex &l, const vertex &r)
  71.         {
  72.             return (l.in < r.in) || (l.in == r.in && l.out > r.out);
  73.         });
  74.  
  75.         int ptr = 1;
  76.         auto *ans = dfs(0, ptr, vs);
  77.  
  78.         vector<ll> ans_vector;
  79.         while (!ans->empty())
  80.             ans_vector.push_back(ans->top()), ans->pop();
  81.         assert(!ans_vector.empty());
  82.         while (int(ans_vector.size()) > n)
  83.             ans_vector.pop_back();
  84.  
  85.         for (int i = 1; i < int(ans_vector.size()); i++)
  86.             ans_vector[i] += ans_vector[i - 1];
  87.  
  88.         while (int(ans_vector.size()) < n)
  89.             ans_vector.push_back(ans_vector.back());
  90.  
  91.         for (ll it  : ans_vector)
  92.             cout << it << ' ';
  93.         cout << endl;
  94.     };
  95.  
  96.     while (solve_test())
  97.     {
  98.         break;
  99.     }
  100. }
  101.  
  102. int main()
  103. {
  104.     ios_base::sync_with_stdio(false);
  105.     cin.tie(nullptr);
  106.  
  107.     cout << fixed;
  108.  
  109. #ifdef LOCAL
  110.     auto st = clock();
  111.  
  112.     ifstream fin("../input.txt");
  113.  
  114.     solve(fin);
  115.  
  116.     cout << "clock: " << setprecision(4) << (clock() - st) / (double) CLOCKS_PER_SEC << endl;
  117. #else
  118.     solve();
  119. #endif
  120.  
  121.     return 0;
  122. }
RAW Paste Data