fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/BBAbFa
language:
C++14 (gcc 8.3)
created:
51 days ago
visibility:
secret

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!