Submission #485270

#	Time	Username	Problem	Language	Result	Execution time	Memory
485270		MilosMilutinovic	Pinball (JOI14_pinball)	C++14	100 / 100	617 ms	30676 KiB

pinball

/**
 *    author: m371
 *    created: 06.11.2021 22:12:33
**/
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const int M = 3 * N;
const int MAX = 4 * M;

const long long inf = 1e18;

long long st[MAX];

void build(int x, int l, int r) {
  st[x] = inf;
  if (l == r) return;
  int mid = l + r >> 1;
  build(x + x, l, mid);
  build(x + x + 1, mid + 1, r);
}

void modify(int x, int l, int r, int pos, long long val) {
  if (l == r) {
    st[x] = min(st[x], val);
    return;
  }
  int mid = l + r >> 1;
  if (pos <= mid) {
    modify(x + x, l, mid, pos, val);
  } else {
    modify(x + x + 1, mid + 1, r, pos, val);
  }
  st[x] = min(st[x + x], st[x + x + 1]);
}

long long get(int x, int l, int r, int ll, int rr) {
  if (l > r || l > rr || r < ll) return inf;
  if (ll <= l && r <= rr) return st[x];
  int mid = l + r >> 1;
  return min(get(x + x, l, mid, ll, rr), get(x + x + 1, mid + 1, r, ll, rr));
} 

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(n), b(n), c(n), cost(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i] >> c[i] >> cost[i];
  }
  vector<int> cs;
  cs.push_back(1);
  cs.push_back(m);
  for (int i = 0; i < n; i++) {
    cs.push_back(a[i]);
    cs.push_back(b[i]);
    cs.push_back(c[i]);
  }
  sort(cs.begin(), cs.end());
  cs.erase(unique(cs.begin(), cs.end()), cs.end());
  map<int, int> val;
  for (int i = 0; i < cs.size(); i++) {
    val[cs[i]] = i;
  }
  build(1, 0, M);
  modify(1, 0, M, val[1], 0);
  vector<long long> L(n), R(n);
  for (int i = 0; i < n; i++) {
    L[i] = get(1, 0, M, val[a[i]], val[b[i]]);
    modify(1, 0, M, val[c[i]], L[i] + cost[i]);
  }
  build(1, 0, M);
  modify(1, 0, M, val[m], 0);
  for (int i = 0; i < n; i++) {
    R[i] = get(1, 0, M, val[a[i]], val[b[i]]);
    modify(1, 0, M, val[c[i]], R[i] + cost[i]);
  }
  long long ans = inf;
  for (int i = 0; i < n; i++) {
    ans = min(ans, L[i] + R[i] + cost[i]);
  }
  cout << (ans == inf ? -1 : ans) << '\n';
  return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'void build(int, int, int)':
pinball.cpp:20:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |   int mid = l + r >> 1;
      |             ~~^~~
pinball.cpp: In function 'void modify(int, int, int, int, long long int)':
pinball.cpp:30:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   int mid = l + r >> 1;
      |             ~~^~~
pinball.cpp: In function 'long long int get(int, int, int, int, int)':
pinball.cpp:42:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |   int mid = l + r >> 1;
      |             ~~^~~
pinball.cpp: In function 'int main()':
pinball.cpp:66:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for (int i = 0; i < cs.size(); i++) {
      |                   ~~^~~~~~~~~~~

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