Submission #548954

#	Time	Username	Problem	Language	Result	Execution time	Memory
548954		Alex_tz307	Pinball (JOI14_pinball)	C++17	100 / 100	265 ms	26280 KiB

pinball

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int INF = 1e18L;

void minSelf(int &x, int y) {
  if (y < x) {
    x = y;
  }
}

struct ST {
  int n;
  vector<int> t;

  ST(int N) : n(N) {
    int dim = 1;
    while (dim < n) {
      dim *= 2;
    }
    t.resize(dim * 2, INF);
  }

  void update(int x, int lx, int rx, int pos, int v) {
    if (lx == rx) {
      minSelf(t[x], v);
      return;
    }
    int mid = (lx + rx) / 2;
    if (pos <= mid) {
      update(x * 2, lx, mid, pos, v);
    } else {
      update(x * 2 + 1, mid + 1, rx, pos, v);
    }
    t[x] = min(t[x * 2], t[x * 2 + 1]);
  }

  void update(int pos, int v) {
    update(1, 1, n, pos, v);
  }

  int query(int x, int lx, int rx, int st, int dr) {
    if (st <= lx && rx <= dr) {
      return t[x];
    }
    int mid = (lx + rx) / 2, ans = INF;
    if (st <= mid) {
      minSelf(ans, query(x * 2, lx, mid, st, dr));
    }
    if (mid < dr) {
      minSelf(ans, query(x * 2 + 1, mid + 1, rx, st, dr));
    }
    return ans;
  }

  int query(int st, int dr) {
    return query(1, 1, n, st, dr);
  }
};

void testCase() {
  int m, n;
  cin >> m >> n;
  vector<int> a(m), b(m), c(m), d(m), v{1, n};
  for (int i = 0; i < m; ++i) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
    v.emplace_back(a[i]);
    v.emplace_back(b[i]);
    v.emplace_back(c[i]);
  }
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  auto getIndex = [&](const int &x) -> int {
    return distance(v.begin(), upper_bound(v.begin(), v.end(), x));
  };
  int N = v.size();
  ST left(N), right(N);
  left.update(1, 0);
  right.update(N, 0);
  int ans = INF;
  for (int i = 0; i < m; ++i) {
    a[i] = getIndex(a[i]);
    b[i] = getIndex(b[i]);
    c[i] = getIndex(c[i]);
    int l = left.query(a[i], b[i]), r = right.query(a[i], b[i]);
    minSelf(ans, l + r + d[i]);
    left.update(c[i], l + d[i]);
    right.update(c[i], r + d[i]);
  }
  if (ans == INF) {
    cout << "-1\n";
  } else {
    cout << ans << '\n';
  }
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

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