Submission #923490

#	Time	Username	Problem	Language	Result	Execution time	Memory
923490		rolandpetrean	Pinball (JOI14_pinball)	C++17	0 / 100	1 ms	344 KiB

pinball

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

using ll = long long;
#define int ll

#define endl '\n'
#define pb push_back
using pi = pair<int, int>;

const int INF = 1e16;

struct SegmentTree {
  int n;
  vector<int> data;
  
  void update(int u, int st, int dr, int p, int x) {
    if (st == dr) data[u] = x;
    else {
      int mid = (st + dr) / 2;
      if (p <= mid) update(2 * u, st, mid, p, x);
      else update(2 * u + 1, mid + 1, dr, p, x);
      data[u] = min(data[2 * u], data[2 * u + 1]);
    }
  }
  void update(int p, int x) {
    update(1, 1, n, p, x);
  }
  int query(int u, int st, int dr, int l, int r) {
    if (st >= l && dr <= r) return data[u];
    int mid = (st + dr) / 2, res = INF;
    if (l <= mid) res = query(2 * u, st, mid, l, r);
    if (mid < r) res = min(res, query(2 * u + 1, mid + 1, dr, l, r));
    return res;
  }
  int query(int l, int r) {
    return query(1, 1, n, l, r);
  }
  
  SegmentTree() {}
  SegmentTree(int n) {
    this->n = n;
    data.assign(4 * (n + 1), INF);
  }
};

struct Device {
  int a, b, c, d;
};

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int m, n;
  cin >> m >> n;
  
  vector<Device> d(m);
  for (int i = 0; i < m; ++i) cin >> d[i].a >> d[i].b >> d[i].c >> d[i].d;

  vector<int> vals{1};
  for (int i = 0; i < m; ++i) vals.insert(vals.end(), {d[i].a, d[i].b, d[i].c});
  vals.pb(n);
  sort(vals.begin(), vals.end());
  vals.erase(unique(vals.begin(), vals.end()), vals.end());
  auto norm = [&](int x) {
    return upper_bound(vals.begin(), vals.end(), x) - vals.begin();
  };
  for (int i = 0; i < m; ++i) {
    d[i].a = norm(d[i].a);
    d[i].b = norm(d[i].b);
    d[i].c = norm(d[i].c);
  }
  n = vals.size();
  
  array<SegmentTree, 2> dp;
  dp[0] = SegmentTree(n);
  dp[1] = SegmentTree(n);
  dp[0].update(1, 0);
  dp[1].update(n, 0);
  
  int ans = INF;
  for (int i = 0; i < m; ++i) {
    int minl = dp[0].query(d[i].a, d[i].b), minr = dp[1].query(d[i].a, d[i].b);
    ans = min(ans, minl + minr + d[i].d);
    
    for (int j = 0; j <= 1; ++j) {
      int mini = dp[j].query(d[i].a, d[i].b);
      dp[j].update(d[i].c, mini + d[i].d);
    }
  }
  
  cout << (ans == INF ? -1 : ans) << endl;
}

/*
5 6
2 4 3 5
1 2 2 8
3 6 5 2
4 6 4 7
2 4 3 10
*/

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