Submission #131746

#	Time	Username	Problem	Language	Result	Execution time	Memory
131746		Just_Solve_The_Problem	Pinball (JOI14_pinball)	C++11	100 / 100	357 ms	38892 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int maxn = (int)5e5 + 7;
const ll inf = (ll)1e18 + 7;

int n, m;
int a[maxn], b[maxn], c[maxn], d[maxn];
int used[maxn];
ll ans;
vector <int> vec;

struct T {
  ll tree[maxn * 4];
  T() {
    for (int i = 0; i < maxn * 4; i++) {
      tree[i] = inf;
    }
  }
  void upd(int pos, ll val, int v = 1, int tl = 0, int tr = maxn - 1) {
    tree[v] = min(tree[v], val);
    if (tl == tr) {
      return ;
    }
    int mid = (tl + tr) >> 1;
    if (pos <= mid) {
      upd(pos, val, v + v, tl, mid);
    } else {
      upd(pos, val, v + v + 1, mid + 1, tr);
    }
  }
  ll get(int l, int r, int v = 1, int tl = 0, int tr = maxn - 1) {
    if (tl > r || tr < l) return inf;
    if (l <= tl && tr <= r) return tree[v];
    int mid = (tl + tr) >> 1;
    return min(get(l, r, v + v, tl, mid), get(l, r, v + v + 1, mid + 1, tr));
  }
};
T l, r;

int getx(int x) {
  return lower_bound(vec.begin(), vec.end(), x) - vec.begin();
}

main() {
  scanf("%d %d", &m, &n);
  for (int i = 0; i < m; i++) {
    scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
    vec.push_back(a[i]);
    vec.push_back(b[i]);
    vec.push_back(c[i]);
  }
  ans = 1e18;
  vec.push_back(1);
  vec.push_back(n);
  sort(vec.begin(), vec.end());
  vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
  l.upd(0, 0);
  r.upd(vec.size() - 1, 0);
  for (int i = 0; i < m; i++) {
    a[i] = getx(a[i]);
    b[i] = getx(b[i]);
    c[i] = getx(c[i]);
    ll left, right;
    tie(left, right) = make_tuple(l.get(a[i], b[i]), r.get(a[i], b[i]));
    ans = min(ans, left + right + d[i]);
    l.upd(c[i], left + d[i]);
    r.upd(c[i], right + d[i]);
  }
  if (ans == (ll)1e18) ans = -1;
  printf("%lld\n", ans);
}

Compilation message (stderr)

pinball.cpp:48:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
pinball.cpp: In function 'int main()':
pinball.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &m, &n);
   ~~~~~^~~~~~~~~~~~~~~~~
pinball.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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