# IOI '18 - Meetings (60pts)

Jul 27th, 2022
801
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include "meetings.h"
2. #include <stack>
3. #include <algorithm>
4.
5. using namespace std;
6.
7. const long long INF = 1e18;
8. const int N = 1e5 + 1, LG = 17 + 1;
9. long long pre[N], suf[N];
10. long long mn[LG][N]; // sparse table of mins over pre[x] + suf[x] in range
11. long long queryMN(int l, int r) {
12.   int i = 0, p2 = 1;
13.   while (p2 <= r-l+1) ++i, p2 <<= 1;
14.   --i, p2 >>= 1;
15.   return min(mn[i][l], mn[i][r-p2+1]);
16. }
17.
18. vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
19.   int Q = L.size(), N = H.size();
20.   vector<long long> C(Q);
21.
22.   if (*max_element(H.begin(), H.end()) <= 20) {
23.     // Convert from zero-based to one-based
24.     H.insert(H.begin(), 0);
25.     for (int &x : L) ++x;
26.     for (int &x : R) ++x;
27.
28.     // Precalculate next and previous of each value from each position
29.     vector<int> nxt[21], prv[21];
30.     for (int i = 0; i <= 20; ++i) {
31.       prv[i] = vector<int>(1+N+1, 0);
32.       nxt[i] = vector<int>(1+N+1, N+1);
33.     }
34.     for (int i = 1; i <= N; ++i) {
35.       for (int j = 1; j <= 20; ++j) prv[j][i] = prv[j][i-1];
36.       prv[H[i]][i] = i;
37.     }
38.     for (int i = N; i >= 1; --i) {
39.       for (int j = 1; j <= 20; ++j) nxt[j][i] = nxt[j][i+1];
40.       nxt[H[i]][i] = i;
41.     }
42.
43.     // Precalculate number with each maximum on each prefix and suffix
44.     vector<int> cntMaxPrefix[21]{}, cntMaxSuffix[21]{};
45.     for (int i = 1; i <= 20; ++i) {
46.       cntMaxPrefix[i].resize(1+N+1);
47.       cntMaxSuffix[i].resize(1+N+1);
48.     }
49.     for (int i = 1; i <= N; ++i) {
50.       cntMaxPrefix[H[i]][i] = 1;
51.       for (int j = 1; j <= H[i]; ++j) cntMaxPrefix[H[i]][i] += cntMaxPrefix[j][i-1];
52.       for (int j = H[i]+1; j <= 20; ++j) cntMaxPrefix[j][i] = cntMaxPrefix[j][i-1];
53.     }
54.     for (int i = N; i >= 1; --i) {
55.       cntMaxSuffix[H[i]][i] = 1;
56.       for (int j = 1; j <= H[i]; ++j) cntMaxSuffix[H[i]][i] += cntMaxSuffix[j][i+1];
57.       for (int j = H[i]+1; j <= 20; ++j) cntMaxSuffix[j][i] = cntMaxSuffix[j][i+1];
58.     }
59.
60.     // Precalculate costs on prefix and suffix
61.     for (int i = 1; i <= N; ++i) {
62.       for (int j = 1; j <= 20; ++j) {
63.         pre[i] += cntMaxPrefix[j][i] * j;
64.         suf[i] += cntMaxSuffix[j][i] * j;
65.       }
66.       suf[i] -= H[i]; // prefix includes this value itself, suffix does not
67.       mn[0][i] = pre[i] + suf[i];
68.     }
69.
70.     // Create sparse table for minimums over range
71.     for (int j = 1, p2 = 1; j < LG; ++j, p2 <<= 1) {
72.       for (int i = 1; i <= N; ++i) {
73.         if (i+p2 > N) mn[j][i] = mn[j-1][i];
74.         else mn[j][i] = min(mn[j-1][i], mn[j-1][i+p2]);
75.       }
76.     }
77.
79.     for (int q = 0; q < Q; ++q) {
80.       int l = L[q], r = R[q];
81.       // Take next of each value from left and previous of each value from right
82.       int soFar = r+1;
83.       vector<pair<int, int>> starts;
84.       for (int j = 20; j >= 1; --j) {
85.         if (nxt[j][l] >= soFar) continue;
86.         soFar = nxt[j][l];
87.         starts.emplace_back(nxt[j][l], j);
88.       }
89.       reverse(starts.begin(), starts.end());
90.
91.       soFar = l-1;
92.       vector<pair<int, int>> ends;
93.       for (int j = 20; j >= 1; --j) {
94.         if (prv[j][r] <= soFar) continue;
95.         soFar = prv[j][r];
96.         ends.emplace_back(prv[j][r], j);
97.       }
98.
100.       for (int start = l, i = 0; i < (int)ends.size(); ++i) {
102.         start = ends[i].first+1;
103.       }
105.
106.       vector<pair<int, int>> merged;
107.       for (int i = 0; i < (int)starts.size(); ++i) merged.emplace_back(starts[i].first, starts[i].second);
108.       for (int i = 0; i < (int)ends.size(); ++i) merged.emplace_back(ends[i].first, -ends[i].second);
109.       sort(merged.begin(), merged.end());
110.
111.
112.       C[q] = INF;
113.       for (int i = 0, curL = 0, curR = 0; i < (int)merged.size(); ++i) {
114.         if (merged[i].second > 0) { // Start
115.           curL = merged[i].second;
116.         } else { // End
117.           curR = -merged[i].second;
118.         }
119.         if (i+1 < (int)merged.size() && merged[i+1].first == merged[i].first) continue;
120.         int rangeL = merged[i].first, rangeR = r;
121.         if (i+1 < (int)merged.size()) rangeR = merged[i+1].first-1;
122.
123.         // now calculate best answer in this range
124.         long long best = queryMN(rangeL, rangeR); // min over pre + suf
125.         // subtract before l and after r
126.         for (int j = 1; j <= 20; ++j) {
127.           best -= cntMaxPrefix[j][l-1] * max(j, curL);
128.           best -= cntMaxSuffix[j][r+1] * max(j, curR);
129.         }
130.         C[q] = min(C[q], best);
131.       }
132.     }
133.   } else {
134.     for (int q = 0; q < Q; ++q) {
135.       int l = L[q], r = R[q];
136.       vector<long long> ans(r-l+1);
137.       stack<int> st;
138.
139.       // Find answer contributions from left
140.       st.push(l-1);
141.       long long sum = 0;
142.       for (int i = l; i <= r; ++i) {
143.         while (st.top() >= l && H[st.top()] <= H[i]) {
144.           int x = st.top();
145.           st.pop();
146.           sum += (long long)(x-st.top())*(H[i]-H[x]);
147.         }
148.         st.push(i);
149.         sum += H[i];
150.         ans[i-l] += sum;
151.       }
152.       while (!st.empty()) st.pop();
153.
154.       // Find answer contributions from right
155.       st.push(r+1);
156.       sum = 0;
157.       for (int i = r; i >= l; --i) {
158.         while (st.top() <= r && H[st.top()] <= H[i]) {
159.           int x = st.top();
160.           st.pop();
161.           sum += (long long)(st.top()-x)*(H[i]-H[x]);
162.         }
163.         st.push(i);
164.         sum += H[i];
165.         ans[i-l] += sum;
166.       }
167.       while (!st.empty()) st.pop();
168.
170.       long long minCost = INF;
171.       for (int i = l; i <= r; ++i) {
172.         ans[i-l] -= H[i]; // counted from both sides
173.         minCost = min(minCost, ans[i-l]);
174.       }
175.       C[q] = minCost;
176.     }
177.   }
178.   return C;
179. }