oj.uz

Submission #261528

# Submission time Handle Problem Language Result Execution time Memory
261528 2020-08-11T20:28:20 Z Haunted_Cpp Fuel Station (NOI20_fuelstation) C++17
13 / 100
 386 ms 70256 KB 
/**
 *  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(d - a);
  }
  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);
  for (int i = 0; i < n; i++) {
    int dist = get<0>(arr[i]) - (i - 1 < 0 ? 0 : get<0>(arr[i - 1]));
    distancias.emplace_back(dist);
    pre.emplace_back(-dist);
    where_is_it[i] = pre.size();
    pre.emplace_back(get<1>(arr[i]));
  }
  pre.emplace_back(-d + get<0>(arr.back()));
  sort(distancias.begin(), distancias.end());
  distancias.erase(unique(distancias.begin(), distancias.end()), distancias.end());
  SegmentTree seg(pre);
  int rem = 0;
  for (auto cur : distancias) {
    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;
    }
  }
  return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 69968 KB Output is correct
2 Correct 282 ms 69968 KB Output is correct
3 Correct 351 ms 69968 KB Output is correct
4 Correct 285 ms 69952 KB Output is correct
5 Correct 328 ms 69964 KB Output is correct
6 Correct 294 ms 69968 KB Output is correct
7 Correct 281 ms 69968 KB Output is correct
8 Correct 386 ms 69944 KB Output is correct
9 Correct 351 ms 69940 KB Output is correct
10 Correct 304 ms 69968 KB Output is correct
11 Correct 296 ms 69968 KB Output is correct
12 Correct 278 ms 69992 KB Output is correct
13 Correct 275 ms 69972 KB Output is correct
14 Correct 279 ms 69968 KB Output is correct
15 Correct 301 ms 70256 KB Output is correct
16 Correct 285 ms 69968 KB Output is correct
17 Correct 293 ms 70096 KB Output is correct
18 Correct 281 ms 69968 KB Output is correct
19 Correct 282 ms 69972 KB Output is correct
20 Correct 280 ms 69968 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -