Submission #856626

#	Time	Username	Problem	Language	Result	Execution time	Memory
856626		kilkuwu	Holiday (IOI14_holiday)	C++17	47 / 100	39 ms	65536 KiB

holiday

#ifndef LOCAL
#include "holiday.h"
#endif

#include <bits/stdc++.h>

#ifdef LOCAL
#include "C:\Users\Admin\Documents\GitHub\HSG\debug.hpp"
#else
#define dbg(...) ;
#endif

using i32 = int;
using i64 = long long;
#define nl '\n'
#define int i64

struct PersistentSegmentTree {
  struct Node {
    int left = 0, right = 0;
    int64_t sum = 0;
    int cnt = 0;
  };

  std::vector<Node> t;
  std::vector<int> values;
  PersistentSegmentTree(const std::vector<int>& a) : t(1), values(a) {}

  int update(int k, int l, int r, int p, int d) {
    int id = t.size();
    t.emplace_back();
    t[id] = t[k];
    if (l == r) {
      t[id].sum += 1LL * values[l] * d;
      t[id].cnt += d;
    } else {
      int mid = (l + r) / 2;
      if (p <= mid) {
        t[id].left = update(t[id].left, l, mid, p, d);
      } else {
        t[id].right = update(t[id].right, mid + 1, r, p, d);
      }
      t[id].sum = t[t[id].left].sum + t[t[id].right].sum;
      t[id].cnt = t[t[id].left].cnt + t[t[id].right].cnt;
    }
    return id;
  }

  int64_t query(int k1, int k2, int l, int r, int how_many) {
    if (l == r) {
      return 1LL * std::min(t[k2].cnt - t[k1].cnt, how_many) * values[l];
    }
    int mid = (l + r) / 2;
    int cnt_right = t[t[k2].right].cnt - t[t[k1].right].cnt;
    if (cnt_right >= how_many) {
      return query(t[k1].right, t[k2].right, mid + 1, r, how_many);
    }
    int64_t sum = t[t[k2].right].sum - t[t[k1].right].sum;
    return sum + query(t[k1].left, t[k2].left, l, mid, how_many - cnt_right);
  }

  int update(int k, int p, int d) {
    return update(k, 0, values.size() - 1, p, d);
  }

  int64_t query(int k1, int k2, int how_many) {
    return query(k1, k2, 0, values.size() - 1, how_many);
  }
};

i64 findMaxAttraction(i32 n, i32 s, i32 d, i32 attraction[]) {
  s++;
  std::vector<int> a(n + 1);
  std::vector<int> vals(n);
  for (int i = 1; i <= n; i++) a[i] = attraction[i - 1], vals[i - 1] = a[i];

  std::sort(vals.begin(), vals.end());
  vals.erase(std::unique(vals.begin(), vals.end()), vals.end());

  auto get_id = [&](int x) -> int {
    return std::lower_bound(vals.begin(), vals.end(), x) - vals.begin();
  };

  PersistentSegmentTree tree(vals);

  std::vector<int> roots = {0};
  for (int i = 1; i <= n; i++) {
    roots.push_back(tree.update(roots.back(), get_id(a[i]), 1));
  }

  int64_t ans = 0;

  auto go = [&](auto self, int ll, int lr, int rl, int rr) -> void {
    if (ll > lr) return;
    if (rl > rr) return;
    int mid = (ll + lr) / 2;
    // go from s to mid and thne
    int64_t best = 0;
    int pos = rr;
    for (int r = rl; r <= rr; r++) {
      int rem = d - (r - mid + std::min(s - mid, r - s));
      if (rem > 0) {
        int64_t cand = tree.query(roots[mid - 1], roots[r], rem);
        if (cand > best) {
          best = cand;
          pos = r;
        }
      }
    }
    ans = std::max(ans, best);
    self(self, ll, mid - 1, rl, pos);
    self(self, mid + 1, lr, pos, rr);
  };

  go(go, 1, s, s, n);
  return ans;
}

#ifdef LOCAL
signed main() {
  freopen("inp", "r", stdin);
  i32 n, s, d;
  std::cin >> n >> s >> d;
  i32 attraction[n];
  for (int i = 0; i < n; i++) std::cin >> attraction[i];
  std::cout << findMaxAttraction(n, s, d, attraction);
}
#endif // LOCAL

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