oj.uz

Submission #261504

# Submission time Handle Problem Language Result Execution time Memory
261504 2020-08-11T19:46:23 Z Haunted_Cpp Fuel Station (NOI20_fuelstation) C++17
13 / 100
 300 ms 71016 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] = 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) {
    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;
    }
  }
  cout << "NO SOLUTION" << '\n';
  return 0;
}

Subtask #1
0 / 7.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 70904 KB Output is correct
2 Correct 272 ms 70916 KB Output is correct
3 Correct 270 ms 70884 KB Output is correct
4 Correct 272 ms 71012 KB Output is correct
5 Correct 277 ms 70892 KB Output is correct
6 Correct 264 ms 71016 KB Output is correct
7 Correct 263 ms 71016 KB Output is correct
8 Correct 300 ms 70884 KB Output is correct
9 Correct 283 ms 70884 KB Output is correct
10 Correct 274 ms 70884 KB Output is correct
11 Correct 278 ms 71012 KB Output is correct
12 Correct 300 ms 70884 KB Output is correct
13 Correct 265 ms 70840 KB Output is correct
14 Correct 295 ms 70888 KB Output is correct
15 Correct 270 ms 70884 KB Output is correct
16 Correct 277 ms 70756 KB Output is correct
17 Correct 280 ms 70884 KB Output is correct
18 Correct 274 ms 70784 KB Output is correct
19 Correct 271 ms 70888 KB Output is correct
20 Correct 269 ms 70784 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 8 ms 2816 KB Output is correct
3 Correct 7 ms 2816 KB Output is correct
4 Correct 7 ms 2848 KB Output is correct
5 Correct 7 ms 2816 KB Output is correct
6 Correct 7 ms 2816 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Incorrect 1 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 8 ms 2816 KB Output is correct
3 Correct 7 ms 2816 KB Output is correct
4 Correct 7 ms 2848 KB Output is correct
5 Correct 7 ms 2816 KB Output is correct
6 Correct 7 ms 2816 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Incorrect 1 ms 384 KB Output isn't correct
9 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 Correct 0 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 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 Correct 0 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 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 Correct 0 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -