Submission #1274943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274943		reginox	Pinball (JOI14_pinball)	C++20	100 / 100	177 ms	42248 KiB

pinball

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
const int MXN = 600000 + 10;
const ll INF = (ll)1e18;

struct Seg {
  vector<ll> t;
  Seg() { t.assign(MXN * 4, INF); }
  void upd(int node, int l, int r, int pos, ll v) {
    if (l == r) { t[node] = min(t[node], v); return; }
    int mid = (l + r) >> 1;
    if (pos <= mid) upd(node<<1, l, mid, pos, v);
    else upd(node<<1|1, mid+1, r, pos, v);
    t[node] = min(t[node<<1], t[node<<1|1]);
  }
  ll query(int node, int l, int r, int ql, int qr) {
    if (ql > qr) return INF;
    if (ql <= l && r <= qr) return t[node];
    int mid = (l + r) >> 1;
    if (qr <= mid) return query(node<<1, l, mid, ql, qr);
    if (ql > mid) return query(node<<1|1, mid+1, r, ql, qr);
    return min(query(node<<1, l, mid, ql, qr), query(node<<1|1, mid+1, r, ql, qr));
  }
};

struct Edge {
  int s, e, c;
  ll w;
};

Seg L, R;
Edge edges[MXN];
vector<int> xs;
ll ans = INF;

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int m, start;
  cin >> m >> start;
  
  xs.push_back(start);
  xs.push_back(1);
  
  for (int i = 1; i <= m; ++i) {
    int s, e, cen;
    ll cost;
    cin >> s >> e >> cen >> cost;
    edges[i].s = s;
    edges[i].e = e;
    edges[i].c = cen;
    edges[i].w = cost;
    xs.push_back(s);
    xs.push_back(cen);
    xs.push_back(e);
  }
  
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  
  for (int i = 1; i <= m; ++i) {
    edges[i].s = int(lower_bound(xs.begin(), xs.end(), edges[i].s) - xs.begin());
    edges[i].e = int(lower_bound(xs.begin(), xs.end(), edges[i].e) - xs.begin());
    edges[i].c = int(lower_bound(xs.begin(), xs.end(), edges[i].c) - xs.begin());
  }

  int maxIdx = (int)xs.size() - 1;
  L.upd(1, 0, maxIdx, 0, 0);
  R.upd(1, 0, maxIdx, maxIdx, 0);
  
  for (int i = 1; i <= m; ++i) {
    ll sum = 0;
    ll d1 = L.query(1, 0, maxIdx, edges[i].s, edges[i].e);
    sum += d1;
    L.upd(1, 0, maxIdx, edges[i].c, d1 + edges[i].w);
    
    ll d2 = R.query(1, 0, maxIdx, edges[i].s, edges[i].e);
    sum += d2;
    R.upd(1, 0, maxIdx, edges[i].c, d2 + edges[i].w);
    
    ans = min(ans, sum + edges[i].w);
  }
  
  if (ans >= INF) cout << -1;
  else cout << ans;
  return 0;
}
  

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