fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long MaxN = 1e5 + 5, INF= 1e18;
  4. long long n,q;
  5. pair<pair<long long, long long>, long long> pr[MaxN];
  6. struct Segment_Tree
  7. {
  8.     vector<long long> st;
  9.     void init(long long n)
  10.     {
  11.         if(n==0) return;
  12.         st.assign(4*n+1,INF);
  13.     }
  14.     void update(long long id, long long l, long long r, long long u, long long val)
  15.     {
  16.         if(l>u||r<u)
  17.         {
  18.             return;
  19.         }
  20.         if(l==r)
  21.         {
  22.             st[id]=min(st[id],val);
  23.             return;
  24.         }
  25.         long long mid = (l+r) >> 1;
  26.         if(u<=mid)
  27.         {
  28.             update(2*id,l,mid,u,val);
  29.         }
  30.         else
  31.         {
  32.             update(2*id+1,mid+1,r,u,val);
  33.         }
  34.         st[id] = min(st[2 * id], st[2 * id + 1]);
  35.     }
  36.     long long get(long long id, long long l, long long r, long long u, long long v)
  37.     {
  38.         if(l>v||r<u)
  39.         {
  40.             return INF;
  41.         }
  42.         if(u<=l&&r<=v)
  43.         {
  44.             return st[id];
  45.         }
  46.         long long mid = (l+r)>>1;
  47.         return min(get(2*id,l,mid,u,v),get(2*id+1,mid+1,r,u,v));
  48.     }
  49.     void update(long long u, long long val)
  50.     {
  51.         update(1,1,n,u,val);
  52.     }
  53.     long long get(long long u, long long v)
  54.     {
  55.         return get(1,1,n,u,v);
  56.     }
  57. };
  58. Segment_Tree segtree;
  59. int main()
  60. {
  61.     ios_base::sync_with_stdio(0);
  62.     cin.tie(0);
  63.     cin >> n >> q;
  64.     segtree.init(n);
  65.     for (long long i=1; i<=q; i++)
  66.     {
  67.         cin >> pr[i].first.second >> pr[i].first.first >> pr[i].second;
  68.     }
  69.     sort(pr+1,pr+q+1);
  70.     for (long long i=1; i<=q; i++)
  71.     {
  72.         long long l = pr[i].first.second,r = pr[i].first.first, c=pr[i].second;
  73.         long long mn;
  74.         if(l-1==0)
  75.         {
  76.             mn=0;
  77.         }
  78.         else
  79.         {
  80.             mn = segtree.get(l-1,r-1);
  81.         }
  82.         segtree.update(r,mn+c);
  83.     }
  84.     long long ans = segtree.get(n,n);
  85.     if(ans!=INF)
  86.     {
  87.         cout << ans;
  88.     }
  89.     else
  90.     {
  91.         cout << -1;
  92.     }
  93. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/bbIN8q
language:
C++14 (gcc 8.3)
created:
15 hours 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!