Submission #1262572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262572		kunzaZa183	Holiday (IOI14_holiday)	C++20	100 / 100	1166 ms	18856 KiB

holiday

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<ll> calc(vector<int> cur) {

  int n = cur.size();
  int maxd = 2 * n + 1;

  vector<pair<int, int>> helper;
  for (int i = 0; i < n; i++) {
    helper.emplace_back(cur[i], i);
  }

  sort(helper.rbegin(), helper.rend());

  vector<int> loc(n);
  for (int i = 0; i < n; i++)
    loc[helper[i].second] = i;

  vector<ll> dp(maxd + 1);
  vector<int> to(maxd + 1);

  vector<array<int, 4>> vpii;
  vpii.push_back({0, maxd, 0, n});
  while (!vpii.empty()) {
    vector<int> ct(4 * n);
    vector<ll> sum(4 * n);

    int qin;
    function<void(int, int, int)> upd = [&](int curin, int curl, int curr) {
      if (qin > curr || qin < curl)
        return;
      if (curl == curr) {
        ct[curin] = 1;
        sum[curin] = helper[curl].first;
        return;
      }

      upd(curin * 2 + 1, curl, (curl + curr) / 2);
      upd(curin * 2 + 2, (curl + curr) / 2 + 1, curr);

      ct[curin] = ct[curin * 2 + 1] + ct[curin * 2 + 2];
      sum[curin] = sum[curin * 2 + 1] + sum[curin * 2 + 2];
    };

    vector<array<int, 4>> vpii2;
    int in = 0;
    for (auto [l, r, mini, maxi] : vpii) {
      int mid = (l + r) / 2;

      auto calc = [&]() {
        ll ans = 0;

        int curin = 0, curl = 0, curr = n - 1;
        int tmpct = mid - (in - 1);
        while (curl != curr) {
          if (ct[2 * curin + 1] >= tmpct) {
            curin = curin * 2 + 1;
            curr = (curl + curr) / 2;
          } else {
            ans += sum[curin * 2 + 1];
            tmpct -= ct[curin * 2 + 1];
            curin = curin * 2 + 2;
            curl = (curl + curr) / 2 + 1;
          }
        }

        if (tmpct >= 1 && ct[curin] >= 1) {
          ans += sum[curin];
        }

        return ans;
      };

      while (in < maxi) {
        ll ans = calc();

        if (ans > dp[mid]) {
          dp[mid] = ans;
          to[mid] = in;
        }

        qin = loc[in];
        upd(0, 0, n - 1);
        in++;
      }

      ll ans = calc();

      if (ans > dp[mid]) {
        dp[mid] = ans;
        to[mid] = in;
      }
    }

    for (auto [l, r, mini, maxi] : vpii) {
      int mid = (l + r) / 2;

      if (l <= mid - 1) {
        vpii2.push_back({l, mid - 1, mini, to[mid]});
      }

      if (mid + 1 <= r) {
        vpii2.push_back({mid + 1, r, to[mid], maxi});
      }
    }

    vpii.swap(vpii2);
  }

  return dp;
}

vector<ll> calc2(vector<int> cur) {

  int n = cur.size();
  int maxd = 3 * n + 1;

  vector<pair<int, int>> helper;
  for (int i = 0; i < n; i++) {
    helper.emplace_back(cur[i], i);
  }

  sort(helper.rbegin(), helper.rend());

  vector<int> loc(n);
  for (int i = 0; i < n; i++)
    loc[helper[i].second] = i;

  vector<ll> dp(maxd + 1);
  vector<int> to(maxd + 1);

  vector<array<int, 4>> vpii;
  vpii.push_back({0, maxd, 0, n});
  while (!vpii.empty()) {
    vector<int> ct(4 * n);
    vector<ll> sum(4 * n);

    int qin;
    function<void(int, int, int)> upd = [&](int curin, int curl, int curr) {
      if (qin > curr || qin < curl)
        return;
      if (curl == curr) {
        ct[curin] = 1;
        sum[curin] = helper[curl].first;
        return;
      }

      upd(curin * 2 + 1, curl, (curl + curr) / 2);
      upd(curin * 2 + 2, (curl + curr) / 2 + 1, curr);

      ct[curin] = ct[curin * 2 + 1] + ct[curin * 2 + 2];
      sum[curin] = sum[curin * 2 + 1] + sum[curin * 2 + 2];
    };

    vector<array<int, 4>> vpii2;
    int in = 0;
    for (auto [l, r, mini, maxi] : vpii) {
      int mid = (l + r) / 2;

      auto calc = [&]() {
        ll ans = 0;

        int curin = 0, curl = 0, curr = n - 1;
        int tmpct = mid - 2 * (in - 1);
        while (curl != curr) {
          if (ct[2 * curin + 1] >= tmpct) {
            curin = curin * 2 + 1;
            curr = (curl + curr) / 2;
          } else {
            ans += sum[curin * 2 + 1];
            tmpct -= ct[2 * curin + 1];
            curin = curin * 2 + 2;
            curl = (curl + curr) / 2 + 1;
          }
        }

        if (tmpct >= 1 && ct[curin] >= 1) {
          ans += sum[curin];
        }

        return ans;
      };

      while (in < maxi) {
        ll ans = calc();

        if (ans > dp[mid]) {
          dp[mid] = ans;
          to[mid] = in;
        }

        qin = loc[in];
        upd(0, 0, n - 1);
        in++;
      }

      ll ans = calc();

      if (ans > dp[mid]) {
        dp[mid] = ans;
        to[mid] = in;
      }
    }

    for (auto [l, r, mini, maxi] : vpii) {
      int mid = (l + r) / 2;

      if (l <= mid - 1) {
        vpii2.push_back({l, mid - 1, mini, to[mid]});
      }

      if (mid + 1 <= r) {
        vpii2.push_back({mid + 1, r, to[mid], maxi});
      }
    }

    vpii.swap(vpii2);
  }

  return dp;
}

long long findMaxAttraction(int n, int start, int d, int attraction[]) {
  vector<int> right;
  for (int i = start; i < n; i++) {
    right.push_back(attraction[i]);
  }
  vector<int> left;
  left.push_back(0);
  for (int i = start - 1; i >= 0; i--) {
    left.push_back(attraction[i]);
  }

  vector<ll> gor = calc(right), backr = calc2(right), gol = calc(left),
             backl = calc2(left);

  ll ans = 0;
  for (int i = 0; i < min(d + 1, (int)gor.size()); i++) {
    ans = max(ans, gor[i] + backl[min(d - i, (int)backl.size() - 1)]);
  }
  for (int i = 0; i < min(d + 1, (int)gol.size()); i++) {
    ans = max(ans, gol[i] + backr[min(d - i, (int)backr.size() - 1)]);
  }

  return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53