Submission #40050

#	Time	Username	Problem	Language	Result	Execution time	Memory
40050		funcsr	Pinball (JOI14_pinball)	C++14	100 / 100	511 ms	23136 KiB

pinball

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define pb push_back
#define INF (1LL<<60)
#define MAX_N (1<<19)
struct SegTree {
  long long seg[MAX_N*2-1];
  SegTree() {
    fill(seg, seg+MAX_N*2-1, INF);
  }
  void chmin(int k, long long v) {
    k += MAX_N-1;
    if (seg[k] <= v) return;
    seg[k] = v;
    while (k) {
      k = (k-1) / 2;
      seg[k] = min(seg[k*2+1], seg[k*2+2]);
    }
  }
  long long query(int a, int b, int k=0, int l=0, int r=MAX_N) {
    if (b <= l || r <= a) return INF;
    if (a <= l && r <= b) return seg[k];
    return min(query(a, b, k*2+1, l, (l+r)/2), query(a, b, k*2+2, (l+r)/2, r));
  }
};

SegTree segL, segR;
int M, N;
int A[100000], B[100000], C[100000], D[100000];
int main() {
  cin >> M >> N;
  rep(i, M) cin >> A[i] >> B[i] >> C[i] >> D[i];
  vector<int> xs;
  rep(i, M) xs.pb(A[i]), xs.pb(B[i]), xs.pb(C[i]);
  xs.pb(1);
  xs.pb(N);
  sort(all(xs)); uniq(xs);
  rep(i, M) A[i] = index(xs, A[i]), B[i] = index(xs, B[i]), C[i] = index(xs, C[i]);
  segR.chmin(xs.size()-1, 0);
  segL.chmin(0, 0);
  long long m = INF;
  rep(i, M) {
    m = min(m, segL.query(A[i], B[i]+1) + segR.query(A[i], B[i]+1) + D[i]);
    segR.chmin(C[i], segR.query(A[i], B[i]+1) + D[i]);
    segL.chmin(C[i], segL.query(A[i], B[i]+1) + D[i]);
  }
  if (m == INF) m = -1;
  cout << m << "\n";
  return 0;
}

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