fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define ll long long//_______________________________________________________________________________________
  5. #define file(name) if(fopen(name".inp","r")) {freopen(name".inp", "r",stdin); freopen(name".out","w",stdout);}//
  6. #define all(x, y) (x).begin() + 1, (x).begin() + (y) + 1                                                      //
  7. #define All(x) (x).begin(), (x).end()                                                                        //
  8. #define el cerr<<'\n';                                                                                        //
  9. #define debug(x) cerr << #x << " = " << x << '\n'                                                             //
  10. #define sevpts signed main                                                                                    //
  11. #define vl vector<int>                                                                                         //
  12. #define pii pair<int, int>                                                                                      //
  13. #define FOR(i,a,b)  for (int i=(a); i<=(b); ++i)                                                              //
  14. #define FOD(i,a,b) for (int i=(a); i>=(b); --i)                                                               //
  15. #define REP(i,n) for (int i = 0; i < (n); ++i)                                                                //
  16. #define pb push_back                                                                                          //
  17. #define fi first//                               __                                                           //
  18. #define se second//                            <(o )____                                                      //
  19. const int MOD2 = 988244353;//                    (  ._> /                                                     //
  20. const int MOD = 1e9 + 7;//                        `----'                                                      //
  21. const long long INF = 2 * 1e9;                                                                               //
  22. const int maxn = 5e5 + 69;                                                                                    //
  23. const int maxn2 = 1e3 + 69;                                                                                   //
  24. //____________________________________________________________________________________________________________//
  25.  
  26. int n;
  27. struct seg {
  28.     vl st;
  29.     vl lazy;
  30.     int n;
  31.  
  32.     seg (int sz) {
  33.         n = sz;
  34.         st.assign(4*n, INF);
  35.         lazy.assign(4*n, INF);
  36.     }
  37.  
  38.     void down (int id) {
  39.         int val = lazy[id];
  40.  
  41.         lazy[2*id] = min(lazy[2*id], val);
  42.         lazy[2*id + 1] = min(lazy[2*id + 1], val);
  43.         st[2*id] = min(st[2*id], val);
  44.         st[2*id + 1] = min(st[2*id + 1], val);
  45.         lazy[id] = INF;
  46.     }
  47.  
  48.     void build (int id, int l, int r, vl & a) {
  49.         if (l == r)
  50.             st[id] = a[l];
  51.         else {
  52.             int mid = l + r >> 1;
  53.             build(2*id, l, mid, a);
  54.             build(2*id + 1, mid+ 1, r, a);
  55.         }
  56.     }
  57.     void build (vl & a) {
  58.         build(1,1,n,a);
  59.     }
  60.  
  61.  
  62.     void upd (int id, int l, int r, int u, int v, int val) {
  63.         if(r < u || l > v)
  64.             return;
  65.  
  66.         if (u <= l && r <= v) {
  67.             lazy[id] = min(lazy[id], val);
  68.             st[id] = min(st[id], val);
  69.         }
  70.         else {
  71.             int mid = l + r >> 1;
  72.             down(id);
  73.             upd(2*id, l, mid, u, v, val);
  74.             upd(2*id + 1, mid + 1, r, u, v, val);
  75.         }
  76.     }
  77.     void upd(int u, int v, int val) {
  78.         upd(1,1,n,u,v,val);
  79.     }
  80.  
  81.  
  82.     ll get (int id, int l, int r, int i) {
  83.         if ( i == 0) return 0;
  84.         if (l == r) return st[id];
  85.         else {
  86.             down(id);
  87.             int mid = l + r >> 1;
  88.             if(i <= mid) {
  89.                 return get(2*id, l, mid, i);
  90.             }
  91.             return get(2*id + 1, mid + 1, r ,i);
  92.         }
  93.     }
  94.     ll get (int i) {
  95.         return get(1,1,n,i);
  96.     }
  97. };
  98.  
  99. struct query {
  100.     ll L, R, C;
  101. };
  102.  
  103. void sibidi() {
  104.     int n, q;
  105.     cin >> n >> q;
  106.     vl dp(maxn);
  107.     fill(All(dp), INF);
  108.     seg tree(n);
  109.     tree.build(dp);
  110.     vector< query > Q(maxn);
  111.     FOR(i,1,q) cin >> Q[i].L >> Q[i].R >> Q[i].C;
  112.     sort(all(Q,q), [] (const query & a, const query & b) {
  113.         return a.L < b.L;
  114.     });
  115.     FOR(i,1,q) {
  116.         ll l = Q[i].L, r = Q[i].R, c = Q[i].C;
  117.         int val = min(tree.get(r), tree.get(l-1) + c);
  118.         tree.upd(l, r, val);
  119.         // debug(i);
  120.         // debug(val);
  121.         // FOR(j,1,n) cerr<<tree.get(j)<<" ";
  122.         // el;
  123.         // el;
  124.  
  125.     }
  126.     if(tree.get(n) == INF) cout<< -1;
  127.     else 
  128.         cout<<tree.get(n);
  129.  
  130. }
  131.  
  132. sevpts(){
  133.     // file("");
  134.     ios_base::sync_with_stdio(false);
  135.     cin.tie(nullptr);
  136.     cout.tie(nullptr);
  137.     int tt = 1;
  138.     //cin >> tt;
  139.     while(tt--)
  140.     sibidi();
  141.     return 0;
  142. }
  143.  
  144.  
Success #stdin #stdout 0.01s 18876KB
comments (?)
stdin
copy 
7 6
4 7 3
1 1 6
6 7 10
4 5 6
1 4 6
1 6 10
stdout
copy 
9
https://ideone.com/U2B9Ll
language:
C++14 (gcc 8.3)
created:
14 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!