oj.uz

Submission #1047653

# Submission time Handle Problem Language Result Execution time Memory
1047653 2024-08-07T14:42:55 Z abczz Treatment Project (JOI20_treatment) C++17
4 / 100
 568 ms 205684 KB 
#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 (a[2] == n ? 1e9 : a[2]+a[0]) < (b[2] == n ? 1e9 : 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];
    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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 205684 KB Output is correct
2 Correct 442 ms 205512 KB Output is correct
3 Correct 399 ms 204708 KB Output is correct
4 Correct 422 ms 204688 KB Output is correct
5 Correct 353 ms 205508 KB Output is correct
6 Correct 423 ms 205596 KB Output is correct
7 Correct 378 ms 205584 KB Output is correct
8 Correct 330 ms 205512 KB Output is correct
9 Correct 352 ms 205508 KB Output is correct
10 Correct 383 ms 205512 KB Output is correct
11 Correct 568 ms 205468 KB Output is correct
12 Correct 532 ms 205564 KB Output is correct
13 Correct 496 ms 205556 KB Output is correct
14 Correct 501 ms 205468 KB Output is correct
15 Correct 470 ms 205596 KB Output is correct
16 Correct 496 ms 205384 KB Output is correct
17 Correct 487 ms 204704 KB Output is correct
18 Correct 555 ms 204736 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 39636 KB Output is correct
2 Incorrect 8 ms 39516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 39636 KB Output is correct
2 Incorrect 8 ms 39516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 205684 KB Output is correct
2 Correct 442 ms 205512 KB Output is correct
3 Correct 399 ms 204708 KB Output is correct
4 Correct 422 ms 204688 KB Output is correct
5 Correct 353 ms 205508 KB Output is correct
6 Correct 423 ms 205596 KB Output is correct
7 Correct 378 ms 205584 KB Output is correct
8 Correct 330 ms 205512 KB Output is correct
9 Correct 352 ms 205508 KB Output is correct
10 Correct 383 ms 205512 KB Output is correct
11 Correct 568 ms 205468 KB Output is correct
12 Correct 532 ms 205564 KB Output is correct
13 Correct 496 ms 205556 KB Output is correct
14 Correct 501 ms 205468 KB Output is correct
15 Correct 470 ms 205596 KB Output is correct
16 Correct 496 ms 205384 KB Output is correct
17 Correct 487 ms 204704 KB Output is correct
18 Correct 555 ms 204736 KB Output is correct
19 Correct 8 ms 39636 KB Output is correct
20 Incorrect 8 ms 39516 KB Output isn't correct
21 Halted 0 ms 0 KB -