제출 #937631

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
937631		vjudge1	Pinball (JOI14_pinball)	C++17	100 / 100	124 ms	30716 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back
#define F first
#define S second
#define pii pair<int, int>
#define all(A) A.begin(), A.end()
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

const int MAXN = 2e5 + 10;
const int INF = 1e18;
const int MOD = 1e9 + 7;
const int mod = 998244353;
const int SQ = 1000;
const int LG = 63;

///////////////////////////////////////

struct baze
{
  int l;
  int r;
  int c;
  int d;
};

baze a[MAXN];
int shokri1[3 * MAXN], shokri2[3 * MAXN], dp1[MAXN], dp2[MAXN], rows, cols;

void upd1(int i, int val)
{
  for (; i < 3 * MAXN; i += i & -i)
    shokri1[i] = min(shokri1[i], val);
}

void upd2(int i, int val)
{
  for (; i >= 1; i -= i & -i)
    shokri2[i] = min(shokri2[i], val);
}

int que1(int i)
{
  int ans = INF;
  for (; i >= 1; i -= i & -i)
    ans = min(ans, shokri1[i]);
  return ans;
}

int que2(int i)
{
  int ans = INF;
  for (; i < 3 * MAXN; i += i & -i)
    ans = min(ans, shokri2[i]);
  return ans;
}

signed main()
{
  fast;
  cin >> rows >> cols;
  for (int i = 1; i <= rows; ++i)
    cin >> a[i].l >> a[i].r >> a[i].c >> a[i].d;
  bool flag = false;
  for (int i = 1; i <= rows; ++i)
    flag |= (a[i].l == 1);
  if (!flag)
    return cout << -1, 0;
  flag = false;
  for (int i = 1; i <= rows; ++i)
    flag |= (a[i].r == cols);
  if (!flag)
    return cout << -1, 0;
  {
    vector<vector<int>> vec;
    for (int i = 1; i <= rows; ++i)
      vec.pb({a[i].l, 0, i}), vec.pb({a[i].r, 1, i}), vec.pb({a[i].c, 2, i});
    sort(all(vec));
    int cnt = 1;
    for (int i = 0; i < vec.size(); ++i)
    {
      if (i > 0 && vec[i][0] != vec[i - 1][0])
        ++cnt;
      auto it = vec[i];
      if (it[1] == 0)
        a[it[2]].l = cnt;
      if (it[1] == 1)
        a[it[2]].r = cnt;
      if (it[1] == 2)
        a[it[2]].c = cnt;
    }
  }
  int mx = 0;
  for (int i = 1; i <= rows; ++i)
  {
    mx = max(mx, a[i].l);
    mx = max(mx, a[i].r);
    mx = max(mx, a[i].c);
    dp1[i] = INF;
    dp2[i] = INF;
  }
  for (int i = 1; i < 3 * MAXN; ++i)
    shokri1[i] = INF, shokri2[i] = INF;
  for (int i = 1; i <= rows; ++i)
  {
    if (a[i].l == 1)
      dp1[i] = a[i].d;
    if (a[i].r == mx)
      dp2[i] = a[i].d;
  }
  int ans = INF;
  for (int i = 1; i <= rows; ++i)
  {
    dp1[i] = min(dp1[i], que2(a[i].l) + a[i].d);
    dp2[i] = min(dp2[i], que1(a[i].r) + a[i].d);
    upd2(a[i].c, dp1[i]);
    upd1(a[i].c, dp2[i]);
    ans = min(ans, dp1[i] + dp2[i] - a[i].d);
  }
  if (ans == INF)
    ans = -1;
  cout << ans << endl;
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

pinball.cpp: In function 'int main()':
pinball.cpp:83:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for (int i = 0; i < vec.size(); ++i)
      |                     ~~^~~~~~~~~~~~

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