oj.uz

Submission #299326

# Submission time Handle Problem Language Result Execution time Memory
299326 2020-09-14T17:47:44 Z AlexPop28 Pinball (JOI14_pinball) C++11
0 / 100
 1 ms 384 KB 
#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

template<class T> void Min(T &a, const T &b) { a = min(a, b); }

const int64_t INF = (int64_t)1e18 + 10;

struct SegmTree {
  struct Node {
    int l = -1, r = -1;
    int64_t val = INF;
  };
  int n;
  vector<Node> t = vector<Node>(1);

  SegmTree(int n_) : n(n_) {}
  
  void Alloc(int &node) {
    if (node != -1) return;
    node = t.size();
    t.emplace_back();
  }
  
  void Recalc(int node) {
    t[node].val = INF;
    int l = t[node].l, r = t[node].r;
    if (l != -1) Min(t[node].val, t[l].val);
    if (r != -1) Min(t[node].val, t[r].val);
  }
  
  void Update(int node, int left, int right, int pos, int64_t val) {
    if (left == right) {
      Min(t[node].val, val);
      return;
    }
    
    int mid = left + (right - left) / 2;
    if (pos <= mid) {
      Alloc(t[node].l);
      Update(t[node].l, left, mid, pos, val);
    } else {
      Alloc(t[node].r);
      Update(t[node].r, mid + 1, right, pos, val);
    }
    Recalc(node);
  }
  
  int64_t Query(int node, int left, int right, int x, int y) {
    if (y < left || x > right) return INF;
    
    if (node == -1) {
      return INF;
    }
    
    if (x <= left && right <= y) {
      return t[node].val;
    }
    
    int mid = left + (right - left) / 2;
    return min(Query(t[node].l, left, mid, x, y),
               Query(t[node].r, mid + 1, right, x, y));
  }
  
  void Update(int pos, int64_t val) {
    Update(0, 0, n - 1, pos, val);
  }
  
  int64_t Query(int l, int r) {
    return Query(0, 0, n - 1, l, r);
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, m; cin >> n >> m;
  vector<int> lft(n), rgt(n), pos(n), cost(n);
  for (int i = 0; i < n; ++i) {
    cin >> lft[i] >> rgt[i] >> pos[i] >> cost[i];
    --lft[i], --rgt[i], --pos[i];
  }

  // final position is monotonic
  // L[i][j] = min cost to be at cell (i, j) if we start in col 1
  // R[i][j] = _"_ col m
  
  SegmTree L(m), R(m);
  L.Update(0, 0);
  R.Update(m - 1, 0);
  
  int64_t ans = INF;
  for (int i = 0; i < n; ++i) {
    int l = lft[i], r = rgt[i], p = pos[i], c = cost[i];
    {
      int64_t curr = L.Query(l, r);
      L.Update(p, curr + c);
    }
    {
      int64_t curr = R.Query(l, r);
      R.Update(p, curr + c);
    }
    int64_t curr_l = L.Query(p, p);
    int64_t curr_r = R.Query(p, p);
    if (curr_l == INF || curr_r == INF) continue;
    ans = min(ans, curr_l + curr_r - c);
  }
  if (ans == INF) ans = -1;
  cout << ans << endl;
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 49.0

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