oj.uz

Submission #261503

# Submission time Handle Problem Language Result Execution time Memory
261503 2020-08-11T19:40:18 Z Haunted_Cpp Fuel Station (NOI20_fuelstation) C++17
13 / 100
 380 ms 79588 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>> top_up(n), arr(n);
  for (int i = 0; i < n; i++) {
    int x, a, b;
    cin >> x >> a >> b;
    top_up[i] = make_tuple(b, a, x);
    arr[i] = make_tuple(x, a, b);
  }
  sort(arr.begin(), arr.end());
  sort(top_up.begin(), top_up.end());
  vector<int> distancias, 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] = arr.size();
    pre.emplace_back(get<1>(arr[i]));
  }
  distancias.emplace_back(d - get<0>(arr.back()));
  pre.emplace_back(-d + get<0>(arr.back()));
  sort(distancias.begin(), 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[rem];
      seg.modify(where, 0);
      ++rem;
    }
    seg.modify(0, cur);
    if (seg.worst_prefix() >= 0) {
      cout << cur << '\n';
      return 0;
    }
  }
  for (auto to : pre) cout << to << ' ' << '\n';
  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 376 ms 79076 KB Output is correct
2 Correct 343 ms 79080 KB Output is correct
3 Correct 344 ms 78820 KB Output is correct
4 Correct 380 ms 79084 KB Output is correct
5 Correct 345 ms 79460 KB Output is correct
6 Correct 340 ms 78436 KB Output is correct
7 Correct 332 ms 78308 KB Output is correct
8 Correct 335 ms 78948 KB Output is correct
9 Correct 343 ms 79460 KB Output is correct
10 Correct 344 ms 78436 KB Output is correct
11 Correct 330 ms 78448 KB Output is correct
12 Correct 337 ms 78952 KB Output is correct
13 Correct 340 ms 78308 KB Output is correct
14 Correct 332 ms 78948 KB Output is correct
15 Correct 343 ms 78948 KB Output is correct
16 Correct 348 ms 79588 KB Output is correct
17 Correct 346 ms 79588 KB Output is correct
18 Correct 336 ms 78964 KB Output is correct
19 Correct 341 ms 79076 KB Output is correct
20 Correct 331 ms 78948 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 -