제출 #1270861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270861		repmann	Pinball (JOI14_pinball)	C++20	51 / 100	136 ms	11428 KiB

pinball

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N, M, K;
struct Device
{
  int a, b, c, d;
}D[100001];
ll ST[2][300001];
inline void Setup()
{
  K = 1;
  while(K < N) K <<= 1;
  for(int i = 1; i < (K + N); i++) ST[0][i] = ST[1][i] = 1e18;
  return;
}
inline void Update(int i, ll x, ll *ST)
{
  i += K - 1;
  ST[i] = min(ST[i], x);
  i >>= 1;
  while(i)
  {
    ST[i] = min(ST[i << 1], ST[i << 1 | 1]);
    i >>= 1;
  }
  return;
}
inline ll Get(int L, int R, ll *ST, int i = 1, int LC = 1, int RC = K)
{
  if((L > RC) || (LC > R)) return 1e18;
  if((L <= LC) && (RC <= R)) return ST[i];
  int S = (LC + RC) >> 1;
  return min(Get(L, R, ST, i << 1, LC, S), Get(L, R, ST, i << 1 | 1, S + 1, RC));
}
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> M >> N;
  for(int i = 1; i <= M; i++) cin >> D[i].a >> D[i].b >> D[i].c >> D[i].d;
  vector <pair <int, ll>> scale;
  for(ll i = 1; i <= M; i++) scale.push_back({D[i].a, (i << 20) + 1});
  for(ll i = 1; i <= M; i++) scale.push_back({D[i].b, (i << 20) + 2});
  for(ll i = 1; i <= M; i++) scale.push_back({D[i].c, (i << 20) + 3});
  sort(scale.begin(), scale.end());
  if((scale[0].first != 1) || (scale[3 * M - 1].first != N)) {cout << "-1\n"; return 0;}
  int prev = 0;
  N = 0;
  for(pair <int, ll> p : scale)
  {
    N += p.first > prev;
    prev = p.first;
    if((p.second & 3) == 1) D[p.second >> 20].a = N;
    if((p.second & 3) == 2) D[p.second >> 20].b = N;
    if((p.second & 3) == 3) D[p.second >> 20].c = N;
  }
  Setup();
  ll sol = 1e18, a, b;
  for(int i = 1; i <= M; i++)
  {
    a = b = 1e18;
    if(D[i].a == 1) a = 0;
    else a = Get(D[i].a, D[i].b, ST[0]);
    if(D[i].b == N) b = 0;
    else b = Get(D[i].a, D[i].b, ST[1]);
    sol = min(a + b + D[i].d, sol);
    Update(D[i].c, Get(D[i].a, D[i].b, ST[0]) + D[i].d, ST[0]);
    Update(D[i].c, Get(D[i].a, D[i].b, ST[1]) + D[i].d, ST[1]);
    if(D[i].a == 1) Update(D[i].c, D[i].d, ST[0]);
    if(D[i].b == N) Update(D[i].c, D[i].d, ST[1]);
  }
  if(sol == 1e18) sol = -1;
  cout << sol << '\n';

  return 0;
}

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