Submission #1210935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210935		loom	Fuel Station (NOI20_fuelstation)	C++20	100 / 100	229 ms	26328 KiB

FuelStation

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 5e18
#define nl '\n'

const int N = 3e5+1;
int seg[4*N], lz[4*N], arr[N];

void lazy(int l, int r, int p){
   if(lz[p] != 0){
      seg[p] += lz[p];
      
      
      if(l != r){
         lz[p*2] += lz[p];
         lz[p*2+1] += lz[p];
      }
      lz[p] = 0;
   }
}

void build(int l, int r, int p){
   if(l == r){
      seg[p] = arr[l];
      return;
   }

   int m = (l+r)/2;
   build(l, m, p*2);
   build(m+1, r, p*2+1);
   seg[p] = min(seg[p*2], seg[p*2+1]);
}

void upd(int l, int r, int p, int ql, int qr, int v){
   lazy(l, r, p);

   if(qr < l or r < ql) return;
   if(ql <= l and r <= qr){
      lz[p] += v;
      lazy(l, r, p);
      return;
   }

   int m = (l+r)/2;
   upd(l, m, p*2, ql, qr, v);
   upd(m+1, r, p*2+1, ql, qr, v);
   seg[p] = min(seg[p*2], seg[p*2+1]);
}

int qry(){
   return -seg[1];
}

void upd(int ql, int qr, int v){
   upd(0, N-1, 1, ql, qr, v);
}

inline void solve(){
   int n, d;
   cin>>n>>d;

   tuple<int,int,int> st[n];
   for(int i=0; i<n; i++){
      int x, a, b;
      cin>>x>>a>>b;
      st[i] = {x, a, b};
   }
   sort(st, st+n);

   for(int i=0; i<n; i++){
      auto [x, a, b] = st[i];
      arr[i] = -x;
   }
   arr[n] = -d;

   for(int i=0; i<n; i++){
      auto [x, a, b] = st[i];
      st[i] = {b, a, i};
   }
   sort(st, st+n, greater<>());

   build(0, N-1, 1);
   int mn = qry();

   for(int i=0; i<n; i++){
      auto [b, a, ix] = st[i];

      upd(ix+1, n, a);
      if(b >= qry()) mn = min(mn, qry());
   }

   cout<<mn;
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   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