Submission #319765

#	Time	Username	Problem	Language	Result	Execution time	Memory
319765		Pety	Pinball (JOI14_pinball)	C++14	0 / 100	1 ms	364 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

int n, m, a[100002], b[100002], c[100002], d[100002];
long long aint[2000002], dp1[100002], dp2[100002];
const long long inf = 1e18;

void update (int nod, int st, int dr, int pozV, long long new_val) {
  if (st == dr)
    aint[nod] = new_val;
  else {
    int med = (st + dr) / 2;
    if (pozV <= med)
      update(2 * nod, st, med, pozV, new_val);
    if (pozV >= med + 1)
      update (2 * nod + 1, med + 1, dr, pozV, new_val);
    aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]);
  }
}

long long query (int nod, int st, int dr, int a, int b) {
  if (a <= st && dr <= b)
    return aint[nod];
  else {
    int med = (st + dr) / 2;
    long long ans = inf;
    if (a <= med)
      ans = min(ans, query(2 * nod, st, med, a, b));
    if (b >= med + 1)
      ans = min(ans, query(2 * nod + 1, med + 1, dr, a, b));
    return ans;
  }
}
map<int, int>mp;

int main ()
{
  cin >> m >> n;
  vector<int>norm;
  norm.push_back(1);
  norm.push_back(n);
  for (int i = 1; i <= m; i++) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
    norm.push_back(a[i]);
    norm.push_back(b[i]);
    norm.push_back(c[i]);
  }
  sort(norm.begin(), norm.end());
  int nr = 0;
  for (int i = 0; i < norm.size(); i++) {
    if (!i || norm[i] != norm[i - 1]) {
      mp[norm[i]] = ++nr;
    }
  }
  for (int i = 1; i <= 4 * nr; i++)
    aint[i] = inf;
  for (int i = 1; i <= m; i++)
    dp1[i] = dp2[i] = inf;
  for (int i = 1; i <= m; i++) {
    if (a[i] == 1)
      dp1[i] = d[i];
    else
      dp1[i] = min(dp1[i], d[i] + query(1, 1, nr, mp[a[i]], mp[b[i]]));
    update(1, 1, nr, mp[c[i]], dp1[i]);
  }
  for (int i = 1; i <= 4 * nr; i++)
    aint[i] = inf;
  for (int i = 1; i <= m; i++) {
    if (b[i] == n)
      dp2[i] = d[i];
    else
      dp2[i] = min(dp2[i], d[i] + query(1, 1, nr, mp[a[i]], mp[b[i]]));
    update(1, 1, nr, mp[c[i]], dp2[i]);
  }
  long long ans = 1e18;
  for (int i = 1; i <= m; i++)
    ans = min(ans, dp1[i] + dp2[i] - d[i]);
  cout << (ans < inf / 100 ? ans : -1) << "\n";
  return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for (int i = 0; i < norm.size(); i++) {
      |                   ~~^~~~~~~~~~~~~

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