oj.uz

Submission #604044

# Submission time Handle Problem Language Result Execution time Memory
604044 2022-07-24T16:09:28 Z erekle Meetings (IOI18_meetings) C++17
60 / 100
 5500 ms 53368 KB 
#include "meetings.h"
#include <stack>
#include <algorithm>

using namespace std;

const long long INF = 1e18;
const int N = 1e5 + 1, LG = 17 + 1;
long long pre[N], suf[N];
long long mn[LG][N]; // sparse table of mins over pre[x] + suf[x] in range
long long queryMN(int l, int r) {
  int i = 0, p2 = 1;
  while (p2 <= r-l+1) ++i, p2 <<= 1;
  --i, p2 >>= 1;
  return min(mn[i][l], mn[i][r-p2+1]);
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
  int Q = L.size(), N = H.size();
  vector<long long> C(Q);

  if (*max_element(H.begin(), H.end()) <= 20) {
    // Convert from zero-based to one-based
    H.insert(H.begin(), 0);
    for (int &x : L) ++x;
    for (int &x : R) ++x;

    // Precalculate next and previous of each value from each position
    vector<int> nxt[21], prv[21];
    for (int i = 0; i <= 20; ++i) {
      prv[i] = vector<int>(1+N+1, 0);
      nxt[i] = vector<int>(1+N+1, N+1);
    }
    for (int i = 1; i <= N; ++i) {
      for (int j = 1; j <= 20; ++j) prv[j][i] = prv[j][i-1];
      prv[H[i]][i] = i;
    }
    for (int i = N; i >= 1; --i) {
      for (int j = 1; j <= 20; ++j) nxt[j][i] = nxt[j][i+1];
      nxt[H[i]][i] = i;
    }

    // Precalculate number with each maximum on each prefix and suffix
    vector<int> cntMaxPrefix[21]{}, cntMaxSuffix[21]{};
    for (int i = 1; i <= 20; ++i) {
      cntMaxPrefix[i].resize(1+N+1);
      cntMaxSuffix[i].resize(1+N+1);
    }
    for (int i = 1; i <= N; ++i) {
      cntMaxPrefix[H[i]][i] = 1;
      for (int j = 1; j <= H[i]; ++j) cntMaxPrefix[H[i]][i] += cntMaxPrefix[j][i-1];
      for (int j = H[i]+1; j <= 20; ++j) cntMaxPrefix[j][i] = cntMaxPrefix[j][i-1];
    }
    for (int i = N; i >= 1; --i) {
      cntMaxSuffix[H[i]][i] = 1;
      for (int j = 1; j <= H[i]; ++j) cntMaxSuffix[H[i]][i] += cntMaxSuffix[j][i+1];
      for (int j = H[i]+1; j <= 20; ++j) cntMaxSuffix[j][i] = cntMaxSuffix[j][i+1];
    }

    // Precalculate costs on prefix and suffix
    for (int i = 1; i <= N; ++i) {
      for (int j = 1; j <= 20; ++j) {
        pre[i] += cntMaxPrefix[j][i] * j;
        suf[i] += cntMaxSuffix[j][i] * j;
      }
      suf[i] -= H[i]; // prefix includes this value itself, suffix does not
      mn[0][i] = pre[i] + suf[i];
    }

    // Create sparse table for minimums over range
    for (int j = 1, p2 = 1; j < LG; ++j, p2 <<= 1) {
      for (int i = 1; i <= N; ++i) {
        if (i+p2 > N) mn[j][i] = mn[j-1][i];
        else mn[j][i] = min(mn[j-1][i], mn[j-1][i+p2]);
      }
    }

    // Answer each query
    for (int q = 0; q < Q; ++q) {
      int l = L[q], r = R[q];
      // Take next of each value from left and previous of each value from right
      int soFar = r+1;
      vector<pair<int, int>> starts;
      for (int j = 20; j >= 1; --j) {
        if (nxt[j][l] >= soFar) continue;
        soFar = nxt[j][l];
        starts.emplace_back(nxt[j][l], j);
      }
      reverse(starts.begin(), starts.end());
      
      soFar = l-1;
      vector<pair<int, int>> ends;
      for (int j = 20; j >= 1; --j) {
        if (prv[j][r] <= soFar) continue;
        soFar = prv[j][r];
        ends.emplace_back(prv[j][r], j);
      }

      vector<pair<int, int>> endsRemade;
      for (int start = l, i = 0; i < (int)ends.size(); ++i) {
        endsRemade.emplace_back(start, ends[i].second);
        start = ends[i].first+1;
      }
      ends = endsRemade;

      vector<pair<int, int>> merged;
      for (int i = 0; i < (int)starts.size(); ++i) merged.emplace_back(starts[i].first, starts[i].second);
      for (int i = 0; i < (int)ends.size(); ++i) merged.emplace_back(ends[i].first, -ends[i].second);
      sort(merged.begin(), merged.end());


      C[q] = INF;
      for (int i = 0, curL = 0, curR = 0; i < (int)merged.size(); ++i) {
        if (merged[i].second > 0) { // Start
          curL = merged[i].second;
        } else { // End
          curR = -merged[i].second;
        }
        if (i+1 < (int)merged.size() && merged[i+1].first == merged[i].first) continue;
        int rangeL = merged[i].first, rangeR = r;
        if (i+1 < (int)merged.size()) rangeR = merged[i+1].first-1;

        // now calculate best answer in this range
        long long best = queryMN(rangeL, rangeR); // min over pre + suf
        // subtract before l and after r
        for (int j = 1; j <= 20; ++j) {
          best -= cntMaxPrefix[j][l-1] * max(j, curL);
          best -= cntMaxSuffix[j][r+1] * max(j, curR);
        }
        C[q] = min(C[q], best);
      }
    }
  } else {
    for (int q = 0; q < Q; ++q) {
      int l = L[q], r = R[q];
      vector<long long> ans(r-l+1);
      stack<int> st;

      // Find answer contributions from left
      st.push(l-1);
      long long sum = 0;
      for (int i = l; i <= r; ++i) {
        while (st.top() >= l && H[st.top()] <= H[i]) {
          int x = st.top();
          st.pop();
          sum += (long long)(x-st.top())*(H[i]-H[x]);
        }
        st.push(i);
        sum += H[i];
        ans[i-l] += sum;
      }
      while (!st.empty()) st.pop();

      // Find answer contributions from right
      st.push(r+1);
      sum = 0;
      for (int i = r; i >= l; --i) {
        while (st.top() <= r && H[st.top()] <= H[i]) {
          int x = st.top();
          st.pop();
          sum += (long long)(st.top()-x)*(H[i]-H[x]);
        }
        st.push(i);
        sum += H[i];
        ans[i-l] += sum;
      }
      while (!st.empty()) st.pop();

      // Choose best answer
      long long minCost = INF;
      for (int i = l; i <= r; ++i) {
        ans[i-l] -= H[i]; // counted from both sides
        minCost = min(minCost, ans[i-l]);
      }
      C[q] = minCost;
    }
  }
  return C;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 239 ms 496 KB Output is correct
11 Correct 698 ms 504 KB Output is correct
12 Correct 214 ms 484 KB Output is correct
13 Correct 654 ms 504 KB Output is correct
14 Correct 105 ms 508 KB Output is correct
15 Correct 136 ms 500 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 47 ms 5452 KB Output is correct
3 Correct 228 ms 51172 KB Output is correct
4 Correct 259 ms 53168 KB Output is correct
5 Correct 208 ms 53060 KB Output is correct
6 Correct 216 ms 53092 KB Output is correct
7 Correct 214 ms 53144 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 47 ms 5452 KB Output is correct
3 Correct 228 ms 51172 KB Output is correct
4 Correct 259 ms 53168 KB Output is correct
5 Correct 208 ms 53060 KB Output is correct
6 Correct 216 ms 53092 KB Output is correct
7 Correct 214 ms 53144 KB Output is correct
8 Correct 348 ms 53120 KB Output is correct
9 Correct 198 ms 53144 KB Output is correct
10 Correct 328 ms 53188 KB Output is correct
11 Correct 353 ms 53188 KB Output is correct
12 Correct 219 ms 53176 KB Output is correct
13 Correct 378 ms 53168 KB Output is correct
14 Correct 244 ms 53200 KB Output is correct
15 Correct 483 ms 53172 KB Output is correct
16 Correct 313 ms 53180 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 239 ms 496 KB Output is correct
11 Correct 698 ms 504 KB Output is correct
12 Correct 214 ms 484 KB Output is correct
13 Correct 654 ms 504 KB Output is correct
14 Correct 105 ms 508 KB Output is correct
15 Correct 136 ms 500 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 47 ms 5452 KB Output is correct
18 Correct 228 ms 51172 KB Output is correct
19 Correct 259 ms 53168 KB Output is correct
20 Correct 208 ms 53060 KB Output is correct
21 Correct 216 ms 53092 KB Output is correct
22 Correct 214 ms 53144 KB Output is correct
23 Correct 348 ms 53120 KB Output is correct
24 Correct 198 ms 53144 KB Output is correct
25 Correct 328 ms 53188 KB Output is correct
26 Correct 353 ms 53188 KB Output is correct
27 Correct 219 ms 53176 KB Output is correct
28 Correct 378 ms 53168 KB Output is correct
29 Correct 244 ms 53200 KB Output is correct
30 Correct 483 ms 53172 KB Output is correct
31 Correct 313 ms 53180 KB Output is correct
32 Execution timed out 5553 ms 53368 KB Time limit exceeded
33 Halted 0 ms 0 KB -