제출 #890093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
890093		vjudge1	Fuel Station (NOI20_fuelstation)	C++14	100 / 100	609 ms	71696 KiB

FuelStation

#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;
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 12 / 12
• Subtask 5: 19 / 19
• Subtask 6: 11 / 11
• Subtask 7: 21 / 21