| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 78669 | imeimi2000 | Meetings (IOI18_meetings) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
1. #include "meetings.h"
2. #include <algorithm>
3. #include <functional>
4.
5. using namespace std;
6. typedef long long llong;
7. typedef pair<int, int> pii;
8.
9. int n;
10.
11. const llong inf = 1e18;
12. vector<llong> ans;
13. pii mx[1 << 21];
14.
15. struct query {
16. int i, l, r;
17. query(int i, int l, int r) : i(i), l(l), r(r) {}
18. };
19.
20. struct line {
21. llong m, b;
22. llong get(int x) const {
23. return m * x + b;
24. }
25. line() {}
26. line(llong m, llong b) : m(m), b(b) {}
27. };
28.
29. struct node {
30. llong lz;
31. line l;
32. llong get(int x) const {
33. return l.get(x);
34. }
35. } seg[1 << 21];
36.
37. vector<query> qs[750001];
38. pii arr[750001];
39.
40. void init(int i, int s, int e) {
41. seg[i].l = line(0, inf);
42. seg[i].lz = 0;
43. if (s == e) {
44. mx[i] = arr[s];
45. return;
46. }
47. int m = (s + e) / 2;
48. init(i << 1, s, m);
49. init(i << 1 | 1, m + 1, e);
50. mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
51. }
52.
53. pii getMax(int i, int s, int e, int x, int y) {
54. if (e < x || y < s) return pii(0, 0);
55. if (x <= s && e <= y) return mx[i];
56. int m = (s + e) / 2;
57. return max(getMax(i << 1, s, m, x, y), getMax(i << 1 | 1, m + 1, e, x, y));
58. }
59.
60.
61. void update(int i, int s, int e, int x, int y, line l) {
62. if (e < x || y < s) return;
63. l.b -= seg[i].lz;
64. int m = (s + e) / 2;
65. if (x <= s && e <= y) {
66. bool A = seg[i].l.get(s) < l.get(s);
67. bool B = seg[i].l.get(m) < l.get(m);
68. if (!B) swap(seg[i].l, l);
69. if (s == e) return;
70. if (A != B) update(i << 1, s, m, x, y, l);
71. else update(i << 1 | 1, m + 1, e, x, y, l);
72. return;
73. }
74. update(i << 1, s, m, x, y, l);
75. update(i << 1 | 1, m + 1, e, x, y, l);
76. }
77.
78. void add(int i, int s, int e, int x, int y, llong v) {
79. if (e < x || y < s) return;
80. if (x <= s && e <= y) {
81. seg[i].lz += v;
82. return;
83. }
84. int m = (s + e) / 2;
85. add(i << 1, s, m, x, y, v);
86. add(i << 1 | 1, m + 1, e, x, y, v);
87. }
88.
89. llong get(int i, int s, int e, int x) {
90. llong ret = seg[i].get(x);
91. if (s == e) return ret + seg[i].lz;
92. int m = (s + e) / 2;
93. if (x <= m) return min(ret, get(i << 1, s, m, x)) + seg[i].lz;
94. return min(ret, get(i << 1 | 1, m + 1, e, x)) + seg[i].lz;
95. }
96.
97. void getQuery(int s, int e) {
98. if (s > e) return;
99. int m = abs(getMax(1, 1, n, s, e).second);
100. getQuery(s, m - 1);
101. getQuery(m + 1, e);
102. for (query q : qs[m]) {
103. ans[q.i] = min(ans[q.i], (q.r > m ? get(1, 1, n, q.r) : 0) + (m - q.l + 1ll) * arr[m].first);
104. }
105. add(1, 1, n, m + 1, e, (m - s + 1ll) * arr[m].first);
106. llong Lm = s < m ? get(1, 1, n, m - 1) : 0;
107. line l(arr[m].first, Lm + (1ll - m) * arr[m].first);
108. update(1, 1, n, m, e, l);
109. }
110.
111. vector<llong> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
112. n = H.size();
113. int q = L.size();
114. ans.resize(q, inf);
115.
116. for (int i = 0; i < n; ++i) arr[i + 1] = pii(H[i], i + 1);
117. init(1, 1, n);
118. for (int i = 0; i < q; ++i) {
119. int mx = getMax(1, 1, n, L[i] + 1, R[i] + 1).second;
120. qs[mx].emplace_back(i, L[i] + 1, R[i] + 1);
121. }
122. getQuery(1, n);
123.
124. for (int i = 1; i <= n; ++i) qs[i].clear();
125.
126. for (int i = 0; i < n; ++i) arr[n - i] = pii(H[i], i - n);
127. init(1, 1, n);
128. for (int i = 0; i < q; ++i) {
129. int mx = -getMax(1, 1, n, n - R[i], n - L[i]).second;
130. qs[mx].emplace_back(i, n - R[i], n - L[i]);
131. }
132. getQuery(1, n);
133. return ans;
134. }