Submission #299336

#	Time	Username	Problem	Language	Result	Execution time	Memory
299336		AlexPop28	Pinball (JOI14_pinball)	C++11	100 / 100	537 ms	55512 KiB

pinball

#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 || 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 = L.Query(l, r), curr_r = R.Query(l, r);
    ans = min(ans, curr_l + curr_r + c);
    
    L.Update(p, curr_l + c);
    R.Update(p, curr_r + c);
  }
  if (ans == INF) ans = -1;
  cout << ans << endl;
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49