oj.uz

Submission #319767

# Submission time Handle Problem Language Result Execution time Memory
319767 2020-11-06T11:51:40 Z Pety Pinball (JOI14_pinball) C++14
0 / 100
 1 ms 364 KB 
#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;
  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  ? ans : -1) << "\n";
  return 0;
}

Compilation message

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -