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. string s;
  9. ll n,m,k,st[4*maxn],lazy[4*maxn],a[maxn],q,dp[maxn];
  10. map<ll,ll> last;
  11. void build(int id = 1, int l = 0, int r = n) {
  12.     if (l == r) {
  13.         st[id] = (l == 0 ? 0 : 1e18); // dp[0] = 0, dp[i>0] = INF
  14.         return;
  15.     }
  16.     int mid = (l + r) / 2;
  17.     build(id*2, l, mid);
  18.     build(id*2+1, mid+1, r);
  19.     st[id] = min(st[id*2], st[id*2+1]);
  20. }
  21. void down(ll id,ll l,ll r,ll mid)
  22. {
  23.     if (lazy[id] != 0)
  24.     {
  25.         lazy[id*2] = lazy[id];
  26.         st[id*2] = lazy[id];
  27.  
  28.         lazy[id*2+1] = lazy[id];
  29.         st[id*2+1] = lazy[id];
  30.  
  31.         lazy[id] = 0;
  32.     }
  33. }
  34. void update(ll pos, ll val, ll id=1, ll l=1, ll r=n)
  35. {
  36.     // [l,r] pos [l,r]
  37.     if (pos < l || r < pos) return;
  38.     if (l == r)
  39.     {
  40.         st[id] = val;
  41.         lazy[id] = val;
  42.         return;
  43.     }
  44.  
  45.     ll mid = (l+r) >> 1;
  46.     // down(id,l,r,mid);
  47.     update(pos,val,id*2,l,mid);
  48.     update(pos,val,id*2+1,mid+1,r);
  49.     st[id] = min(st[id*2] , st[id*2+1]);
  50. }
  51. ll get(ll u, ll v,ll id=1,ll l=1, ll r=n)
  52. {
  53.     if (u > r || v < l) return 1e18;
  54.     if (u <= l && r <= v) return st[id];
  55.     ll mid = (l+r) >> 1;
  56.     // down(id,l,r,mid);
  57.     return min(get(u,v,id*2,l,mid) , get(u,v,id*2+1,mid+1,r));
  58. }
  59.  
  60. // cần tìm st[id] < l bên trái nhất là do cần tìm giá trị nhỏ nhất
  61. ll walkleft(ll u, ll v, ll k,ll id=1,ll l=1,ll r=n)
  62. {
  63.     // ST[ID] vẫn còn trong đoạn l,r
  64.     if (v < l || u > r || st[id] >= k) return -1;
  65.     if (l == r) return l;
  66.     ll mid = (l+r) >> 1;
  67.     ll ret = walkleft(u,v,k,id*2,l,mid);
  68.     if (ret == -1) ret = walkleft(u,v,k,id*2+1,mid+1,r);
  69.     return ret; 
  70. }
  71.  
  72. struct query
  73. {
  74.     ll l,r,c;
  75. }Q[maxn];
  76. bool cmp(query x, query y)
  77. {
  78.     return x.r < y.r;
  79. }
  80. main()
  81. {
  82.     ios_base::sync_with_stdio(false);
  83.     cin.tie(NULL);
  84.     file("test");
  85.     cin >> n >> q;
  86.     for (int i=1;i<=q;i++) cin >> Q[i].l >> Q[i].r >> Q[i].c;
  87.     build();
  88.     // for (int i=1;i<=n;i++) update(i,1e18);
  89.     // update(0,1e18);
  90.     sort(Q + 1, Q + q + 1, cmp);
  91.  
  92.     for (auto p:Q) {
  93.         ll l = p.l;
  94.         ll r = p.r;
  95.         ll c = p.c;
  96.  
  97.         for (ll j = l; j <= r; j++) 
  98.         {
  99.             ll cur = get(j, j);
  100.             ll best = get(l - 1, j - 1); // lấy dp[j] với j trong [l-1, j-1]
  101.             if (best + c < cur) {
  102.                 update(j, best + c);
  103.             }
  104.         }
  105.     }   
  106.     ll ans = get(n,n);
  107.     if (ans != 1e18) cout << ans;
  108.     else cout << -1;
  109.  
  110.     return 0;
  111. }
Success #stdin #stdout 0.01s 8004KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EB2fZ6
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!