fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ii pair<ll,ll>
  3. #define iii pair<ll,pair<ll,ll>>
  4. #define ll long long
  5. #define file(a) freopen(a".inp","r",stdin);freopen(a".out","w",stdout);
  6. using namespace std;
  7. const int maxn = 1e6+5;
  8. const int dx[] = {-1,0,0,1};
  9. const int dy[] = {0,-1,1,0};
  10. ll n,m,st[maxn*4],q,lazy[maxn*4];
  11. struct Query { ll l, r, c; } Q[maxn];
  12. bool cmp(Query a, Query b) { return a.r < b.r; }
  13.  
  14.  
  15. void build(ll id = 1, ll l = 0, ll r = n) {
  16.     lazy[id] = 1e18;
  17.     if (l == r) {
  18.         st[id] = (l == 0 ? 0 : 1e18);
  19.         return;
  20.     }
  21.     ll mid = (l + r) >> 1;
  22.     build(id*2, l, mid);
  23.     build(id*2+1, mid+1, r);
  24.     st[id] = min(st[id*2], st[id*2+1]);
  25. }
  26. void push(ll id, ll l, ll r) 
  27. {
  28.     if (lazy[id] != 1e18) {
  29.         st[id] = min(st[id], lazy[id]);
  30.         if (l != r) {
  31.             lazy[id*2] = min(lazy[id*2], lazy[id]);
  32.             lazy[id*2+1] = min(lazy[id*2+1], lazy[id]);
  33.         }
  34.         lazy[id] = 1e18;
  35.     }
  36. }
  37. void update(ll u, ll v, ll val, ll id=1, ll l=0, ll r=n)
  38. {
  39.     push(id,l,r);
  40.     // [u,v] [l,r] [u,v]
  41.     if (u > r || l > v) return;
  42.     if (u <= l && r <= v)
  43.     {
  44.         // st[id] = val;
  45.         lazy[id] = val;
  46.         push(id,l,r);
  47.         return;
  48.     }
  49.     // down(id);
  50.     ll mid = (l+r) >> 1;
  51.     update(u,v,val,id*2,l,mid);
  52.     update(u,v,val,id*2+1,mid+1,r);
  53.     st[id] = min(st[id*2],st[id*2+1]);
  54. }
  55.  
  56. ll get(ll u, ll v,ll id=1,ll l=0, ll r=n)
  57. {
  58.     push(id,l,r);
  59.     if (u > r || v < l) return 1e18;
  60.     if (u <= l && r <= v) return st[id];
  61.     ll mid = (l+r) >> 1;
  62.     // down(id);
  63.     return min(get(u,v,id*2,l,mid), get(u,v,id*2+1,mid+1,r));
  64. }
  65. main()
  66. {
  67.     ios_base::sync_with_stdio(false);
  68.     cin.tie(NULL);
  69.     cin >> n >> q;
  70.     for (int i = 1; i <= q; ++i)
  71.         cin >> Q[i].l >> Q[i].r >> Q[i].c;
  72.  
  73.     build();
  74.     sort(Q + 1, Q + q + 1, cmp);
  75.     for (auto p:Q)
  76.     {
  77.         ll l = p.l;
  78.         ll r = p.r;
  79.         ll c = p.c;
  80.  
  81.         // for (int i=l;i<=r;i++)
  82.         // {
  83.         //     ll cur = get(i,i);
  84.         //     ll best = get(max(0LL,l-1),i-1);
  85.         //     if (best != 1e18 && best + c < cur)
  86.         //     {
  87.         //         update(i,best + c);
  88.         //     }
  89.         // }
  90.         ll best = get(max(0ll,l-1),r-1);
  91.         if (best != 1e18) update(l,r,best + c);
  92.     }
  93.     ll ans = get(n,n);
  94.     if (ans != 1e18) cout << ans;
  95.     else cout << -1;
  96.     return 0;
  97. }
Success #stdin #stdout 0.02s 5524KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Skj2S3
language:
C++14 (gcc 8.3)
created:
2 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!