Submission #241195

#	Time	Username	Problem	Language	Result	Execution time	Memory
241195		rama_pang	Holiday (IOI14_holiday)	C++14	100 / 100	459 ms	4608 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;

class SegmentTree {
 private:
  int sz;
  vector<int> data;
  vector<int> mapping;
  vector<int> reverse_mapping;

  vector<int> cnt;
  vector<long long> tree;

  long long KthLargestSum(int n, int tl, int tr, int k) {
    if (k <= 0) return 0;
    if (tl == tr || k == cnt[n]) return tree[n];
    int md = (tl + tr) / 2;
    int z = n + 2 * (md - tl + 1);
    return KthLargestSum(n + 1, tl, md, k - cnt[z]) +
           KthLargestSum(z, md + 1, tr, min(cnt[z], k));
  }

  void Toggle(int n, int tl, int tr, int p, bool act) {
    if (tl == tr) {
      if (act) {
        tree[n] = data[reverse_mapping[tl]];
        cnt[n] = 1;
      } else {
        tree[n] = cnt[n] = 0;
      }
      return;
    }
    int md = (tl + tr) / 2;
    int z = n + 2 * (md - tl + 1);
    if (p <= md) {
      Toggle(n + 1, tl, md, p, act);
    } else {
      Toggle(z, md + 1, tr, p, act);
    }
    tree[n] = tree[n + 1] + tree[z];
    cnt[n] = cnt[n + 1] + cnt[z];
  }

 public:
  SegmentTree() {}
  SegmentTree(vector<int> data_) : data(data_) {
    sz = data.size();
    reverse_mapping.resize(sz);
    iota(begin(reverse_mapping), end(reverse_mapping), 0);
    sort(begin(reverse_mapping), end(reverse_mapping), [&](int i, int j) { return data[i] < data[j]; });
    mapping.resize(sz);
    for (int i = 0; i < sz; i++) {
      mapping[reverse_mapping[i]] = i;
    }
    tree.assign(2 * sz, 0);
    cnt.assign(2 * sz, 0);
  }

  long long KthLargestSum(int k) {
    return KthLargestSum(1, 0, sz - 1, k);
  }

  void Toggle(int i, bool act) {
    return Toggle(1, 0, sz - 1, mapping[i], act);
  }
};

int N, S, D;
SegmentTree T;
long long ans;

long long FindCost(int s, int e, int d) {
  if (d < 0) return -1;
  static int l = 0, r = -1;
  while (r < e) T.Toggle(++r, 1);
  while (l > s) T.Toggle(--l, 1);
  while (r > e) T.Toggle(r--, 0);
  while (l < s) T.Toggle(l++, 0);
  return T.KthLargestSum(d);
}

void Solve(int sl, int sr, int el, int er) {
  if (sl > sr) return;
  int sm = (sl + sr) / 2;
  int em = el;
  long long cur = -1;
  for (int e = el; e <= er; e++) {
    long long res = FindCost(sm, e, D - (e - sm) - min(S - sm, e - S));
    if (res > cur) {
      cur = res;
      em = e;
    }
  }
  ans = max(ans, cur);
  return Solve(sl, sm - 1, el, em), Solve(sm + 1, sr, em, er);
}

long long findMaxAttraction(int n, int start, int d, int attraction[]) {
  N = n, S = start, D = d;
  T = SegmentTree(vector<int>(attraction, attraction + n));
  Solve(0, start, start, N - 1);
  return ans;
}

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