Submission #1047731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047731		abczz	Treatment Project (JOI20_treatment)	C++17	4 / 100	532 ms	204484 KiB

treatment

#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#define ll long long

using namespace std;

ll n, m, f, cur, dp[100000], X[100000];
array <ll, 5> A[100000];

struct SegTree1D{
  vector <ll> st;
  void init(ll sz) {
    st.resize(4*sz);
    fill(st.begin(), st.end(), (ll)1e18);
  }
  void update(ll id, ll l, ll r, ll q, ll w) {
    if (l == r) {
      st[id] = min(st[id], w);
      return;
    }
    ll mid = (l+r)/2;
    if (q <= mid) update(id*2, l, mid, q, w);
    else update(id*2+1, mid+1, r, q, w);
    st[id] = min(st[id*2], st[id*2+1]);
  }
  ll query(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql) return 1e18;
    else if (ql <= l && r <= qr) return st[id];
    ll mid = (l+r)/2;
    return min(query(id*2, l, mid, ql, qr), query(id*2+1, mid+1, r, ql, qr));
  }
};
struct SegTree2D{
  vector <ll> V[400000];
  SegTree1D st[400000];
  void build(ll id, ll l, ll r) {
    st[id].init(r-l+1);
    if (l == r) {
      V[id].push_back(X[l]);
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    int i = 0, j = 0;
    while (i < V[id*2].size() && j < V[id*2+1].size()) {
      if (V[id*2][i] <= V[id*2+1][j]) V[id].push_back(V[id*2][i++]);
      else V[id].push_back(V[id*2+1][j++]);
    }
    while (i < V[id*2].size()) V[id].push_back(V[id*2][i++]);
    while (j < V[id*2+1].size()) V[id].push_back(V[id*2+1][j++]);
  }
  void update(ll id, ll l, ll r, ll x, ll q, ll w) {
    auto it = lower_bound(V[id].begin(), V[id].end(), q);
    st[id].update(1, 0, V[id].size()-1, it-V[id].begin(), w);
    if (l == r) return;
    ll mid = (l+r)/2;
    if (x <= mid) update(id*2, l, mid, x, q, w);
    else update(id*2+1, mid+1, r, x, q, w);
  }
  ll query(ll id, ll l, ll r, ll ql, ll qr, ll x) {
    if (qr < l || r < ql) return 1e18;
    else if (ql <= l && r <= qr) {
      auto it = lower_bound(V[id].begin(), V[id].end(), x);
      if (it != V[id].end()) return st[id].query(1, 0, V[id].size()-1, it-V[id].begin(), V[id].size()-1);
      else return 1e18;
    }
    ll mid = (l+r)/2;
    return min(query(id*2, l, mid, ql, qr, x), query(id*2+1, mid+1, r, ql, qr, x));
  }
}STA, STB;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  f = 1e18;
  cin >> n >> m;
  for (int i=0; i<m; ++i) {
    for (int j=0; j<4; ++j) {
      cin >> A[i][j];
    }
  }
  sort(A, A+m);
  for (int i=0; i<m; ++i) A[i][4] = i;
  for (int i=0; i<m; ++i) X[i] = A[i][2]+A[i][0];
  STA.build(1, 0, m-1);
  for (int i=0; i<m; ++i) X[i] = A[i][2]-A[i][0];
  STB.build(1, 0, m-1);
  sort(A, A+m, [](auto a, auto b) {
    return (ll)(a[2] == n ? 1e18 : a[2]+a[0]) < (ll)(b[2] == n ? 1e18 : b[2]+b[0]);
  });
  for (int i=0; i<m; ++i) {
    cur = STA.query(1, 0, m-1, 0, A[i][4], A[i][1]+A[i][0]-1);
    if (A[i][4] != m-1) cur = min(cur, STB.query(1, 0, m-1, A[i][4]+1, m-1, A[i][1]-A[i][0]-1));
    dp[i] = cur+A[i][3];
    if (A[i][1] == 1) dp[i] = A[i][3];
    //cout << A[i][1] << " " << A[i][2] << " " << dp[i] << endl;
    if (A[i][2] == n) f = min(f, dp[i]);
    STA.update(1, 0, m-1, A[i][4], A[i][2]+A[i][0], dp[i]);
    STB.update(1, 0, m-1, A[i][4], A[i][2]-A[i][0], dp[i]);
  }
  if (f >= 1e18) cout << "-1\n";
  else cout << f << '\n';
}

Compilation message (stderr)

treatment.cpp: In member function 'void SegTree2D::build(long long int, long long int, long long int)':
treatment.cpp:48:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     while (i < V[id*2].size() && j < V[id*2+1].size()) {
      |            ~~^~~~~~~~~~~~~~~~
treatment.cpp:48:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     while (i < V[id*2].size() && j < V[id*2+1].size()) {
      |                                  ~~^~~~~~~~~~~~~~~~~~
treatment.cpp:52:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     while (i < V[id*2].size()) V[id].push_back(V[id*2][i++]);
      |            ~~^~~~~~~~~~~~~~~~
treatment.cpp:53:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     while (j < V[id*2+1].size()) V[id].push_back(V[id*2+1][j++]);
      |            ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 61