oj.uz

Submission #241195

# Submission time Handle Problem Language Result Execution time Memory
241195 2020-06-23T09:07:57 Z rama_pang Holiday (IOI14_holiday) C++14
100 / 100
 459 ms 4608 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 4608 KB Output is correct
2 Correct 44 ms 4608 KB Output is correct
3 Correct 44 ms 4608 KB Output is correct
4 Correct 45 ms 4608 KB Output is correct
5 Correct 55 ms 4344 KB Output is correct
6 Correct 20 ms 1536 KB Output is correct
7 Correct 30 ms 2560 KB Output is correct
8 Correct 37 ms 3072 KB Output is correct
9 Correct 14 ms 1152 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct
2 Correct 8 ms 512 KB Output is correct
3 Correct 8 ms 512 KB Output is correct
4 Correct 12 ms 512 KB Output is correct
5 Correct 9 ms 512 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 4600 KB Output is correct
2 Correct 53 ms 4608 KB Output is correct
3 Correct 94 ms 2304 KB Output is correct
4 Correct 9 ms 512 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 456 ms 4600 KB Output is correct
9 Correct 459 ms 4600 KB Output is correct