제출 #890093

#제출 시각아이디문제언어결과실행 시간메모리
890093vjudge1Fuel Station (NOI20_fuelstation)C++14
100 / 100
609 ms71696 KiB
#include<bits/stdc++.h>

using namespace std;

#define int long long

struct Node{
   int val, lazy;
   Node(int x=1e18, int y=0){
      val=x;
      lazy=y;
   }
   friend Node operator+(const Node &a, const Node &b){
      return Node(min(a.val, b.val));
   }
};

struct SegmentTree{
   int n;
   vector<Node> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, Node());
   }
   void build(int k, int l, int r, const vector<int> &a){
      if (l==r){
         t[k].val=-a[l];
         return;
      }
      int mid=(l+r)>>1;
      build(k<<1, l, mid, a);
      build(k<<1|1, mid+1, r, a);
      t[k]=t[k<<1]+t[k<<1|1];
   }
   void apply(int k, int val){
      t[k].val+=val;
      t[k].lazy+=val;
   }
   void push(int k){
      if (t[k].lazy){
         apply(k<<1, t[k].lazy);
         apply(k<<1|1, t[k].lazy);
         t[k].lazy=0;
      }
   }
   void update(int k, int l, int r, int L, int R, int val){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         apply(k, val);
         return;
      }
      push(k);
      int mid=(l+r)>>1;
      update(k<<1, l, mid, L, R, val);
      update(k<<1|1, mid+1, r, L, R, val);
      t[k]=t[k<<1]+t[k<<1|1];
   }
   Node get(int k, int l, int r, int L, int R){
      if (r<L || R<l) return t[0];
      if (L<=l && r<=R) return t[k];
      push(k);
      int mid=(l+r)>>1;
      return get(k<<1, l, mid, L, R)+get(k<<1|1, mid+1, r, L, R);
   }
} st;

const int N=3e5+1;
int n, d, x[N], a[N], b[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> d;
   vector<int> pos{-1, d};
   map<int, vector<int>> mp;
   for (int i=1; i<=n; ++i) cin >> x[i] >> a[i] >> b[i], pos.push_back(x[i]), mp[-b[i]].push_back(i);
   sort(pos.begin(), pos.end());
   pos.resize(unique(pos.begin(), pos.end())-pos.begin());
   int ans=d;
   st.init((int)pos.size()-1);
   st.build(1, 1, st.n, pos);
   for (auto &i:mp){
      for (int j:i.second) st.update(1, 1, st.n, lower_bound(pos.begin(), pos.end(), x[j])-pos.begin()+1, st.n, a[j]);
      if (-i.first+st.t[1].val>=0) ans=min(ans, -st.t[1].val);
   }
   cout << ans;
   return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...