oj.uz

Submission #883176

# Submission time Handle Problem Language Result Execution time Memory
883176 2023-12-04T17:26:35 Z MilosMilutinovic Long Distance Coach (JOI17_coach) C++14
100 / 100
 191 ms 81680 KB 
#include <bits/stdc++.h>
 
using namespace std;

struct line {
  __int128 k, n;
  line(__int128 _k = 0, __int128 _n = 0) : k(_k), n(_n) {}
  __int128 val(__int128 x) {
    return k * x + n;
  }
};

const int MAX = 2e6;

int root, ls[MAX], rs[MAX], tsz;
line st[MAX];

void Modify(int& x, long long l, long long r, line ln) {
  if (!x) {
    x = ++tsz;
    st[x] = line(0, (__int128) 2e18);
  }
  long long mid = l + r >> 1;
  if (st[x].val(mid) > ln.val(mid)) {
    swap(st[x], ln);
  }
  if (l == r) {
    return;
  }
  if (st[x].val(l) > ln.val(l)) {
    Modify(ls[x], l, mid, ln);
  } else {
    Modify(rs[x], mid + 1, r, ln);
  }
}

__int128 Query(int x, long long l, long long r, long long i) {
  if (!x) {
    return (__int128) 1e18;
  }
  if (l == r) {
    return st[x].val(i);
  }
  long long mid = l + r >> 1;
  if (i <= mid) {
    return min(st[x].val(i), Query(ls[x], l, mid, i));
  } else {
    return min(st[x].val(i), Query(rs[x], mid + 1, r, i));
  }
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long x, t;
  int n, m, w;
  cin >> x >> n >> m >> w >> t;
  vector<long long> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  s.push_back(x);
  n += 1;
  m += 1;
  vector<long long> d(m);
  vector<int> c(m);
  for (int i = 1; i < m; i++) {
    cin >> d[i] >> c[i];
  }
  d[0] = 0;
  c[0] = 0;
  vector<int> order(m);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    return d[i] < d[j];
  });
  {
    vector<long long> new_d(m);
    vector<int> new_c(m);
    for (int i = 0; i < m; i++) {
      new_d[i] = d[order[i]];
      new_c[i] = c[order[i]];
    }
    d = new_d;
    c = new_c;
  }
  const long long inf = (long long) 1e18;
  vector<long long> fir(m, inf);
  for (int i = 0; i < n; i++) {
    int low = 0, high = m - 1, idx = -1;
    while (low <= high) {
      int mid = low + high >> 1;
      if (d[mid] < (s[i] % t)) {
        idx = mid;
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    if (idx != -1) {
      fir[idx] = min(fir[idx], s[i] / t);
    }
  }
  vector<__int128> dp(m);
  dp[0] = (__int128) (x / t + 1) * (__int128) w;
  long long sum_c = 0;
  for (int i = 1; i < m; i++) {
    dp[i] = dp[i - 1] + (__int128) ((x - d[i]) / t + 1) * (__int128) w;
    Modify(root, 0, (long long) 1e12, line(-((i - 1) * 1LL * w), dp[i - 1] - sum_c));
    sum_c += c[i];
    if (fir[i] != inf) {
      dp[i] = min(dp[i], Query(root, 0, (long long) 1e12, fir[i]) + (__int128) fir[i] * (__int128) i * (__int128)w + sum_c);
    }
  }
  cout << (long long) dp[m - 1] << '\n';
  return 0;
}

Compilation message

coach.cpp: In function 'void Modify(int&, long long int, long long int, line)':
coach.cpp:23:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |   long long mid = l + r >> 1;
      |                   ~~^~~
coach.cpp: In function '__int128 Query(int, long long int, long long int, long long int)':
coach.cpp:44:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |   long long mid = l + r >> 1;
      |                   ~~^~~
coach.cpp: In function 'int main()':
coach.cpp:92:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |       int mid = low + high >> 1;
      |                 ~~~~^~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 64088 KB Output is correct
2 Correct 8 ms 64092 KB Output is correct
3 Correct 8 ms 64124 KB Output is correct
4 Correct 8 ms 64176 KB Output is correct
5 Correct 9 ms 64092 KB Output is correct
6 Correct 8 ms 64092 KB Output is correct
7 Correct 8 ms 64092 KB Output is correct
8 Correct 9 ms 64160 KB Output is correct
9 Correct 8 ms 64192 KB Output is correct
10 Correct 8 ms 64088 KB Output is correct
11 Correct 8 ms 64092 KB Output is correct
12 Correct 8 ms 64088 KB Output is correct
13 Correct 9 ms 64092 KB Output is correct
14 Correct 9 ms 64092 KB Output is correct
15 Correct 8 ms 64088 KB Output is correct
16 Correct 8 ms 64088 KB Output is correct
17 Correct 8 ms 64148 KB Output is correct
18 Correct 9 ms 64092 KB Output is correct
19 Correct 8 ms 64124 KB Output is correct
20 Correct 8 ms 64092 KB Output is correct
21 Correct 9 ms 64248 KB Output is correct
22 Correct 8 ms 64204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 64088 KB Output is correct
2 Correct 8 ms 64092 KB Output is correct
3 Correct 8 ms 64124 KB Output is correct
4 Correct 8 ms 64176 KB Output is correct
5 Correct 9 ms 64092 KB Output is correct
6 Correct 8 ms 64092 KB Output is correct
7 Correct 8 ms 64092 KB Output is correct
8 Correct 9 ms 64160 KB Output is correct
9 Correct 8 ms 64192 KB Output is correct
10 Correct 8 ms 64088 KB Output is correct
11 Correct 8 ms 64092 KB Output is correct
12 Correct 8 ms 64088 KB Output is correct
13 Correct 9 ms 64092 KB Output is correct
14 Correct 9 ms 64092 KB Output is correct
15 Correct 8 ms 64088 KB Output is correct
16 Correct 8 ms 64088 KB Output is correct
17 Correct 8 ms 64148 KB Output is correct
18 Correct 9 ms 64092 KB Output is correct
19 Correct 8 ms 64124 KB Output is correct
20 Correct 8 ms 64092 KB Output is correct
21 Correct 9 ms 64248 KB Output is correct
22 Correct 8 ms 64204 KB Output is correct
23 Correct 8 ms 64092 KB Output is correct
24 Correct 8 ms 64092 KB Output is correct
25 Correct 8 ms 64092 KB Output is correct
26 Correct 8 ms 64196 KB Output is correct
27 Correct 8 ms 64092 KB Output is correct
28 Correct 8 ms 64248 KB Output is correct
29 Correct 10 ms 64092 KB Output is correct
30 Correct 8 ms 64092 KB Output is correct
31 Correct 8 ms 64092 KB Output is correct
32 Correct 8 ms 64108 KB Output is correct
33 Correct 9 ms 64092 KB Output is correct
34 Correct 8 ms 64128 KB Output is correct
35 Correct 8 ms 64088 KB Output is correct
36 Correct 9 ms 64252 KB Output is correct
37 Correct 8 ms 64092 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 64088 KB Output is correct
2 Correct 8 ms 64092 KB Output is correct
3 Correct 8 ms 64124 KB Output is correct
4 Correct 8 ms 64176 KB Output is correct
5 Correct 9 ms 64092 KB Output is correct
6 Correct 8 ms 64092 KB Output is correct
7 Correct 8 ms 64092 KB Output is correct
8 Correct 9 ms 64160 KB Output is correct
9 Correct 8 ms 64192 KB Output is correct
10 Correct 8 ms 64088 KB Output is correct
11 Correct 8 ms 64092 KB Output is correct
12 Correct 8 ms 64088 KB Output is correct
13 Correct 9 ms 64092 KB Output is correct
14 Correct 9 ms 64092 KB Output is correct
15 Correct 8 ms 64088 KB Output is correct
16 Correct 8 ms 64088 KB Output is correct
17 Correct 8 ms 64148 KB Output is correct
18 Correct 9 ms 64092 KB Output is correct
19 Correct 8 ms 64124 KB Output is correct
20 Correct 8 ms 64092 KB Output is correct
21 Correct 9 ms 64248 KB Output is correct
22 Correct 8 ms 64204 KB Output is correct
23 Correct 8 ms 64092 KB Output is correct
24 Correct 8 ms 64092 KB Output is correct
25 Correct 8 ms 64092 KB Output is correct
26 Correct 8 ms 64196 KB Output is correct
27 Correct 8 ms 64092 KB Output is correct
28 Correct 8 ms 64248 KB Output is correct
29 Correct 10 ms 64092 KB Output is correct
30 Correct 8 ms 64092 KB Output is correct
31 Correct 8 ms 64092 KB Output is correct
32 Correct 8 ms 64108 KB Output is correct
33 Correct 9 ms 64092 KB Output is correct
34 Correct 8 ms 64128 KB Output is correct
35 Correct 8 ms 64088 KB Output is correct
36 Correct 9 ms 64252 KB Output is correct
37 Correct 8 ms 64092 KB Output is correct
38 Correct 9 ms 64348 KB Output is correct
39 Correct 10 ms 64560 KB Output is correct
40 Correct 9 ms 64312 KB Output is correct
41 Correct 11 ms 64264 KB Output is correct
42 Correct 9 ms 64256 KB Output is correct
43 Correct 10 ms 64188 KB Output is correct
44 Correct 9 ms 64188 KB Output is correct
45 Correct 9 ms 64348 KB Output is correct
46 Correct 11 ms 64396 KB Output is correct
47 Correct 10 ms 64348 KB Output is correct
48 Correct 10 ms 64348 KB Output is correct
49 Correct 9 ms 64364 KB Output is correct
50 Correct 10 ms 64388 KB Output is correct
51 Correct 9 ms 64344 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 64088 KB Output is correct
2 Correct 8 ms 64092 KB Output is correct
3 Correct 8 ms 64124 KB Output is correct
4 Correct 8 ms 64176 KB Output is correct
5 Correct 9 ms 64092 KB Output is correct
6 Correct 8 ms 64092 KB Output is correct
7 Correct 8 ms 64092 KB Output is correct
8 Correct 9 ms 64160 KB Output is correct
9 Correct 8 ms 64192 KB Output is correct
10 Correct 8 ms 64088 KB Output is correct
11 Correct 8 ms 64092 KB Output is correct
12 Correct 8 ms 64088 KB Output is correct
13 Correct 9 ms 64092 KB Output is correct
14 Correct 9 ms 64092 KB Output is correct
15 Correct 8 ms 64088 KB Output is correct
16 Correct 8 ms 64088 KB Output is correct
17 Correct 8 ms 64148 KB Output is correct
18 Correct 9 ms 64092 KB Output is correct
19 Correct 8 ms 64124 KB Output is correct
20 Correct 8 ms 64092 KB Output is correct
21 Correct 9 ms 64248 KB Output is correct
22 Correct 8 ms 64204 KB Output is correct
23 Correct 8 ms 64092 KB Output is correct
24 Correct 8 ms 64092 KB Output is correct
25 Correct 8 ms 64092 KB Output is correct
26 Correct 8 ms 64196 KB Output is correct
27 Correct 8 ms 64092 KB Output is correct
28 Correct 8 ms 64248 KB Output is correct
29 Correct 10 ms 64092 KB Output is correct
30 Correct 8 ms 64092 KB Output is correct
31 Correct 8 ms 64092 KB Output is correct
32 Correct 8 ms 64108 KB Output is correct
33 Correct 9 ms 64092 KB Output is correct
34 Correct 8 ms 64128 KB Output is correct
35 Correct 8 ms 64088 KB Output is correct
36 Correct 9 ms 64252 KB Output is correct
37 Correct 8 ms 64092 KB Output is correct
38 Correct 9 ms 64348 KB Output is correct
39 Correct 10 ms 64560 KB Output is correct
40 Correct 9 ms 64312 KB Output is correct
41 Correct 11 ms 64264 KB Output is correct
42 Correct 9 ms 64256 KB Output is correct
43 Correct 10 ms 64188 KB Output is correct
44 Correct 9 ms 64188 KB Output is correct
45 Correct 9 ms 64348 KB Output is correct
46 Correct 11 ms 64396 KB Output is correct
47 Correct 10 ms 64348 KB Output is correct
48 Correct 10 ms 64348 KB Output is correct
49 Correct 9 ms 64364 KB Output is correct
50 Correct 10 ms 64388 KB Output is correct
51 Correct 9 ms 64344 KB Output is correct
52 Correct 184 ms 77916 KB Output is correct
53 Correct 162 ms 80212 KB Output is correct
54 Correct 164 ms 79840 KB Output is correct
55 Correct 179 ms 80568 KB Output is correct
56 Correct 175 ms 81268 KB Output is correct
57 Correct 166 ms 80604 KB Output is correct
58 Correct 166 ms 80148 KB Output is correct
59 Correct 164 ms 80180 KB Output is correct
60 Correct 165 ms 79112 KB Output is correct
61 Correct 167 ms 80480 KB Output is correct
62 Correct 169 ms 80616 KB Output is correct
63 Correct 148 ms 79856 KB Output is correct
64 Correct 118 ms 81208 KB Output is correct
65 Correct 145 ms 81356 KB Output is correct
66 Correct 126 ms 80964 KB Output is correct
67 Correct 151 ms 81460 KB Output is correct
68 Correct 155 ms 79976 KB Output is correct
69 Correct 191 ms 79924 KB Output is correct
70 Correct 175 ms 80172 KB Output is correct
71 Correct 181 ms 80376 KB Output is correct
72 Correct 174 ms 79936 KB Output is correct
73 Correct 176 ms 79948 KB Output is correct
74 Correct 183 ms 81680 KB Output is correct
75 Correct 162 ms 81020 KB Output is correct
76 Correct 158 ms 80056 KB Output is correct
77 Correct 176 ms 80848 KB Output is correct
78 Correct 176 ms 81092 KB Output is correct
79 Correct 175 ms 80696 KB Output is correct
80 Correct 178 ms 80180 KB Output is correct