Submission #287798

#	Time	Username	Problem	Language	Result	Execution time	Memory
287798		Haunted_Cpp	Fuel Station (NOI20_fuelstation)	C++17	100 / 100	926 ms	89548 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:22:24: warning: statement has no effect [-Wunused-value]
   22 |     #define debug(...) 47
      |                        ^~
FuelStation.cpp:117:9: note: in expansion of macro 'debug'
  117 |         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