Submission #1147929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147929		fryingduc	Pinball (JOI14_pinball)	C++20	100 / 100	198 ms	45100 KiB

pinball

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e5 + 5;
int n, m, a[maxn], b[maxn], c[maxn], d[maxn];
int va[maxn], vb[maxn], vc[maxn];
pair<int, long long> fl[maxn], fr[maxn];

struct segment_tree {
  int n; 
  vector<pair<int, long long>> tree;
  segment_tree() {}
  segment_tree(int n) : n(n), tree(n * 4 + 6, make_pair(1e9, 1e18)) {}
  void update(int pos, pair<int, long long> val, int ind, int l, int r) {
    if (l == r) {
      tree[ind] = min(tree[ind], val);
      return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) {
      update(pos, val, ind << 1, l, mid);
    } else {
      update(pos, val, ind << 1 | 1, mid + 1, r);
    }
    tree[ind] = min(tree[ind << 1], tree[ind << 1 | 1]);
  }
  
  pair<int, long long> get(int x, int y, int ind, int l, int r) {
    if (l > y || r < x) return make_pair(1e9, 1e18);
    if (x <= l and r <= y) {
      return tree[ind];
    }
    int mid = (l + r) >> 1;
    return min(get(x, y, ind << 1, l, mid), get(x, y, ind << 1 | 1, mid + 1, r));
  }
  
  void update(int pos, pair<int, long long> val) {
    update(pos, val, 1, 1, n);
  }
  
  pair<int, long long> get(int x, int y) {
    return get(x, y, 1, 1, n);
  }
} smn, smx;

void solve() {
  cin >> n >> m;
  vector<int> vec;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
    vec.push_back(a[i]);
    vec.push_back(b[i]);
    vec.push_back(c[i]);
  }
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  for (int i = 1; i <= n; ++i) {
    va[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
    vb[i] = lower_bound(vec.begin(), vec.end(), b[i]) - vec.begin() + 1;
    vc[i] = lower_bound(vec.begin(), vec.end(), c[i]) - vec.begin() + 1;
  }
  smx = smn = segment_tree((int)vec.size());
  long long res = 1e18;
  for (int i = 1; i <= n; ++i) {
    fl[i] = make_pair(a[i], d[i]);
    fr[i] = make_pair(-b[i], d[i]);
    pair<int, long long> x = smn.get(va[i], vb[i]); x.second += d[i];
    fl[i] = min(fl[i], x);
    x = smx.get(va[i], vb[i]); x.second += d[i];
    fr[i] = min(fr[i], x);
    if (fl[i].first == 1 and fr[i].first == -m) {
      res = min(res, fl[i].second + fr[i].second - d[i]);
    }
    smn.update(vc[i], fl[i]);
    smx.update(vc[i], fr[i]);
  }
  cout << (res == 1e18 ? -1 : res);
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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