Submission #1222834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222834		madamadam3	Meetings (IOI18_meetings)	C++20	0 / 100	372 ms	851968 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1e18;

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

  vector<int> queries(Q); iota(queries.begin(), queries.end(), 0); 
  sort(queries.begin(), queries.end(), [&](int a, int b) {return R[a] < R[b];}); 

  vector<vector<ll>> left_stacks(n), right_stacks(n);
  vector<ll> stL(n, 0), stR(n, 0);
  int cur_query = 0;
  for (int i = 0; i < n; i++) {
    int cur_idx = i - 1;
    while (cur_idx >= 0 && stL[cur_idx] < H[i]) {
      stL[cur_idx] = H[i];
      cur_idx--;
    }

    stL[i] = H[i];
    left_stacks[i] = stL;
  }

  for (int i = n-1; i >= 0; i--) {
    int cur_idx = i+1;
    while (cur_idx < n && stR[cur_idx] < H[i]) {
      stR[cur_idx] = H[i];
      cur_idx++;
    }

    stR[i] = H[i];
    right_stacks[i] = stR;
  }

  for (int st = 0; st < n; st++) {
    for (int i = 1; i < n; i++) {
      left_stacks[st][i] += left_stacks[st][i-1];
    }
    for (int i = n - 2; i >= 0; i--) {
      right_stacks[st][i] += right_stacks[st][i+1];
    }
  }

  auto f = [&](int i, int j) {
    ll lv = left_stacks[i][i], rv = right_stacks[i][i];
    ll lsub = L[j] == 0 ? 0 : left_stacks[i][L[j] - 1], rsub = R[j] == n - 1 ? 0 : right_stacks[i][R[j] + 1];

    lv -= lsub; rv -= rsub;
    return lv + rv - H[i];
  };

  for (int j = 0; j < Q; ++j) {
    int lo = L[j], hi = R[j]-1;

    while (lo < hi) {
      int mid = lo + (hi - lo) / 2;
      int m2 = mid + 1;

      if (f(mid, j) > f(m2, j)) {
        lo = mid+1;
      } else {
        hi = mid;
      }
    }

    C[j] = f(lo, j);
  }

  return C;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40