fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #ifdef natural_selection
  5. #include "../libra/misc/dbg.h"
  6. #else
  7. #define debug(...)
  8. #define endl "\n"
  9. #endif
  10.  
  11. template <typename Info, typename Tag>
  12. class SegTreeChan
  13. {
  14. public:
  15. int n;
  16. vector<Info> infos;
  17. vector<Tag> tags;
  18.  
  19. template<typename O>
  20. void Recurse(int lb, int rb, bool update, O op)
  21. {
  22. auto rec = [&](int v, int l, int r, auto &&rec) -> void
  23. {
  24. Propagate(v, l, r);
  25.  
  26. if(l > r)
  27. return;
  28.  
  29. if(lb <= l and r <= rb)
  30. {
  31. op(v, l, r);
  32. return;
  33. }
  34.  
  35. int m = (l + r)/2;
  36.  
  37. if(m >= lb)
  38. rec(2 * v, l, m, rec);
  39. else if(update)
  40. Propagate(2 * v, l, m);
  41.  
  42. if(m + 1 <= rb)
  43. rec(2 * v + 1, m + 1, r, rec);
  44. else if(update)
  45. Propagate(2 * v + 1, m + 1, r);
  46.  
  47. if(update)
  48. infos[v] = infos[2 * v].Unite(infos[2 * v + 1]);
  49. };
  50. rec(1, 0, n - 1, rec);
  51. };
  52.  
  53. SegTreeChan() : SegTreeChan(0) {};
  54. SegTreeChan(int n) : SegTreeChan(vector<Info> (n)) {};
  55. SegTreeChan(const vector<Info> &a) :
  56. n((int)a.size()), infos(4 * n + 5), tags(4 * n + 5)
  57. {
  58. auto build = [&](int v, int l, int r, auto &&build) -> void
  59. {
  60. if(l > r)
  61. return;
  62. if(l == r)
  63. {
  64. infos[v] = Info(a[l]);
  65. return;
  66. }
  67. int m = (l + r)/2;
  68. build(v * 2, l, m, build);
  69. build(v * 2 + 1, m + 1, r, build);
  70. infos[v] = infos[v * 2].Unite(infos[v * 2 + 1]);
  71. };
  72. build(1, 0, n - 1, build);
  73. };
  74.  
  75. void Propagate(int v, int l, int r)
  76. {
  77. if(tags[v].Empty())
  78. return;
  79. tags[v].ApplyTo(infos[v], l, r);
  80. if(l != r)
  81. {
  82. tags[v].ApplyTo(tags[2 * v]);
  83. tags[v].ApplyTo(tags[2 * v + 1]);
  84. }
  85. tags[v] = Tag();
  86. }
  87.  
  88. void Modify(int lb, int rb, const Tag &tag)
  89. {
  90. Recurse(lb, rb, true, [&](int v, int l, int r)
  91. {
  92. tag.ApplyTo(tags[v]);
  93. Propagate(v, l, r);
  94. });
  95. }
  96. void Set(int p, const Info &info)
  97. {
  98. Recurse(p, p, true, [&](int v, int l, int r)
  99. {
  100. infos[v] = info;
  101. });
  102. }
  103. void Add(int p, const Info &info)
  104. {
  105. Recurse(p, p, true, [&](int v, int l, int r)
  106. {
  107. infos[v] = infos[v].Unite(info);
  108. Propagate(v, l, r);
  109. });
  110. }
  111. Info Query(int lb, int rb)
  112. {
  113. Info res = Info();
  114. Recurse(lb, rb, false, [&](int v, int l, int r)
  115. {
  116. res = res.Unite(infos[v]);
  117. });
  118. return res;
  119. }
  120. Info Get(int p)
  121. {
  122. Info res = Info();
  123. Recurse(p, p, false, [&](int v, int l, int r)
  124. {
  125. res = infos[v];
  126. });
  127. return res;
  128. }
  129. };
  130.  
  131. const int64_t inf = numeric_limits<int64_t>::max();
  132.  
  133. class InfoChan
  134. {
  135. public:
  136. pair<int64_t, int> mn;
  137.  
  138. InfoChan() : mn(make_pair(inf, -1)) {}; //if second element is -1, it means no element
  139. InfoChan(int i, int64_t x) : mn(x, i) {};
  140.  
  141. InfoChan Unite(InfoChan b) const
  142. {
  143. InfoChan res;
  144. if(mn.second == -1)
  145. res.mn = b.mn;
  146. else if(b.mn.second == -1)
  147. res.mn = mn;
  148. else
  149. res.mn = min(mn, b.mn);
  150. return res;
  151. }
  152. static InfoChan GetDefault([[maybe_unused]] int l, [[maybe_unused]] int r)
  153. {
  154. return InfoChan();
  155. }
  156. };
  157. class TagChan
  158. {
  159. public:
  160. int64_t paint;
  161.  
  162. TagChan() : paint(inf) {};
  163. TagChan(int x) : paint(x) {};
  164.  
  165. bool ApplyTo(InfoChan &a, [[maybe_unused]] int l, [[maybe_unused]] int r) const
  166. {
  167. if(a.mn.second != -1)
  168. a.mn.first = min(a.mn.first, paint);
  169. return true;
  170. }
  171. void ApplyTo(TagChan &t) const
  172. {
  173. t.paint = min(t.paint, paint);
  174. }
  175. bool Empty() const
  176. {
  177. return paint == inf;
  178. }
  179. };
  180.  
  181.  
  182. int32_t main()
  183. {
  184. ios_base::sync_with_stdio(false), cin.tie(NULL);
  185.  
  186. int n, m;
  187. cin >> n >> m;
  188.  
  189. vector<vector<array<int, 3>>> adj(n);
  190. for(int i = 0; i < m; i ++)
  191. {
  192. int u, l, r, c;
  193. cin >> u >> l >> r >> c;
  194. -- u, -- l, -- r, c;
  195. adj[u].push_back({l, r, c});
  196. }
  197.  
  198. vector<InfoChan> a(n);
  199. for(int i = 0; i < n; i ++)
  200. a[i].mn = {(i == 0 ? 0 : inf), i};
  201.  
  202. SegTreeChan<InfoChan, TagChan> rq(a);
  203.  
  204. vector<int64_t> dis(n);
  205.  
  206. for(int i = 0; i < n; i ++)
  207. {
  208. auto [d, u] = rq.Query(0, n - 1).mn;
  209. dis[u] = d;
  210.  
  211. assert(u != -1);
  212.  
  213. for(auto [l, r, c] : adj[u])
  214. rq.Modify(l, r, TagChan(d + c));
  215.  
  216. rq.Set(u, InfoChan());
  217. }
  218.  
  219. for(int u = 0; u < n; u ++)
  220. cout << dis[u] << " ";
  221. cout << endl;
  222. }
Runtime error #stdin #stdout #stderr 0.01s 5288KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc