Submission #261524

#	Time	Username	Problem	Language	Result	Execution time	Memory
261524		Haunted_Cpp	Fuel Station (NOI20_fuelstation)	C++17	100 / 100	996 ms	82756 KiB

FuelStation

/**
 *  author: Haunted_Cpp
**/
 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
 
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif

class SegmentTree {
private:
  struct Node {
    long long prefix, sum, best;
    Node () {
      prefix = sum = best = 1e9;
    }
    void merge(Node l, Node r) {
      prefix = min(l.prefix, l.sum + r.prefix);
      sum = l.sum + r.sum;
      best = min({l.best, prefix});
    }
  };
  vector<Node> seg;
  const int LO, HI;
  void build(int l, int r, int node, const vector<int> &arr) {
    if (l == r) {
      seg[node].prefix = seg[node].sum = seg[node].best = arr[l];
      return;
    }
    const int mid = l + (r - l) / 2;
    build(l, mid, 2 * node + 1, arr);
    build(mid + 1, r, 2 * node + 2, arr);
    seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
  }
  void modify(int where, int delta, int l, int r, int node) {
    if (l > where || r < where) return;
    if (l >= where && r <= where) {
      seg[node].prefix = seg[node].sum = seg[node].best = delta;
      return;
    }
    const int mid = l + (r - l) / 2;
    modify(where, delta, l, mid, 2 * node + 1);
    modify(where, delta, mid + 1, r, 2 * node + 2);
    seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
  }
public:
  SegmentTree(const vector<int> &arr) : LO(0), HI((int)arr.size() - 1) {
    seg.clear();
    seg.resize(4 * (int) arr.size());
    build(LO, HI, 0, arr);
  }
  void modify(int where, int delta) {
    modify(where, delta, LO, HI, 0);
  }
  long long worst_prefix() {
    return seg[0].best;
  } 
};

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, d;
  cin >> n >> d;
  vector<tuple<int, int, int>> arr(n);
  vector<pair<int, int>> top_up;
  vector<int> distancias;
  for (int i = 0; i < n; i++) {
    int x, a, b;
    cin >> x >> a >> b;
    arr[i] = make_tuple(x, a, b);
    distancias.emplace_back(x);
    distancias.emplace_back(a);
    distancias.emplace_back(b);
    distancias.emplace_back(d - a);
    distancias.emplace_back(d - b);
  }
  sort(arr.begin(), arr.end());
  for (int i = 0; i < n; i++) top_up.emplace_back(get<2>(arr[i]), i);
  sort(top_up.begin(), top_up.end());
  vector<int> pre = {0};
  vector<int> where_is_it(n);
  long long s = 0;
  for (int i = 0; i < n; i++) {
    int dist = get<0>(arr[i]) - (i - 1 < 0 ? 0 : get<0>(arr[i - 1]));
    s += dist;
    distancias.emplace_back(max(0, dist - get<1>(arr[i - 1])));
    distancias.emplace_back(s);
    distancias.emplace_back(dist);
    pre.emplace_back(-dist);
    where_is_it[i] = pre.size();
    pre.emplace_back(get<1>(arr[i]));
  }
  distancias.emplace_back(d - get<0>(arr.back()));
  pre.emplace_back(-d + get<0>(arr.back()));
  distancias.emplace_back(d);
  sort(distancias.begin(), distancias.end());
  distancias.erase(unique(distancias.begin(), distancias.end()), distancias.end());
  SegmentTree seg(pre);
  int rem = 0;
  for (auto cur : distancias) {
    debug("TEST: ", cur);
    while(rem < n && get<0>(top_up[rem]) < cur) {
      const int where = where_is_it[get<1>(top_up[rem])];
      seg.modify(where, 0);
      ++rem;
    }
    seg.modify(0, cur);
    if (seg.worst_prefix() >= 0) {
      cout << cur << '\n';
      return 0;
    }
  }
  cout << "NO SOLUTION" << '\n';
  return 0;
}

Compilation message (stderr)

FuelStation.cpp: In function 'int main()':
FuelStation.cpp:117:25: warning: statement has no effect [-Wunused-value]
     debug("TEST: ", cur);
                         ^

• 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