Advertisement
erek1e

IOI '18 - Meetings (60pts)

Jul 27th, 2022
636
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.73 KB | None | 0 0
  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.  
  78.     // Answer each query
  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.  
  99.       vector<pair<int, int>> endsRemade;
  100.       for (int start = l, i = 0; i < (int)ends.size(); ++i) {
  101.         endsRemade.emplace_back(start, ends[i].second);
  102.         start = ends[i].first+1;
  103.       }
  104.       ends = endsRemade;
  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.  
  169.       // Choose best answer
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement