oj.uz

Submission #1047731

# Submission time Handle Problem Language Result Execution time Memory
1047731 2024-08-07T15:25:33 Z abczz Treatment Project (JOI20_treatment) C++17
4 / 100
 532 ms 204484 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 (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

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 428 ms 204228 KB Output is correct
2 Correct 450 ms 204232 KB Output is correct
3 Correct 399 ms 203720 KB Output is correct
4 Correct 401 ms 203552 KB Output is correct
5 Correct 345 ms 204244 KB Output is correct
6 Correct 337 ms 204240 KB Output is correct
7 Correct 387 ms 204100 KB Output is correct
8 Correct 334 ms 204096 KB Output is correct
9 Correct 344 ms 204232 KB Output is correct
10 Correct 385 ms 204228 KB Output is correct
11 Correct 532 ms 204284 KB Output is correct
12 Correct 527 ms 204484 KB Output is correct
13 Correct 480 ms 204232 KB Output is correct
14 Correct 490 ms 204144 KB Output is correct
15 Correct 467 ms 204080 KB Output is correct
16 Correct 467 ms 204228 KB Output is correct
17 Correct 458 ms 203972 KB Output is correct
18 Correct 526 ms 204024 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 204228 KB Output is correct
2 Correct 450 ms 204232 KB Output is correct
3 Correct 399 ms 203720 KB Output is correct
4 Correct 401 ms 203552 KB Output is correct
5 Correct 345 ms 204244 KB Output is correct
6 Correct 337 ms 204240 KB Output is correct
7 Correct 387 ms 204100 KB Output is correct
8 Correct 334 ms 204096 KB Output is correct
9 Correct 344 ms 204232 KB Output is correct
10 Correct 385 ms 204228 KB Output is correct
11 Correct 532 ms 204284 KB Output is correct
12 Correct 527 ms 204484 KB Output is correct
13 Correct 480 ms 204232 KB Output is correct
14 Correct 490 ms 204144 KB Output is correct
15 Correct 467 ms 204080 KB Output is correct
16 Correct 467 ms 204228 KB Output is correct
17 Correct 458 ms 203972 KB Output is correct
18 Correct 526 ms 204024 KB Output is correct
19 Correct 5 ms 39516 KB Output is correct
20 Correct 5 ms 39516 KB Output is correct
21 Correct 6 ms 39512 KB Output is correct
22 Incorrect 5 ms 39516 KB Output isn't correct
23 Halted 0 ms 0 KB -