Submission #885222

#	Time	Username	Problem	Language	Result	Execution time	Memory
885222		NeroZein	Holiday (IOI14_holiday)	C++17	100 / 100	541 ms	5716 KiB

holiday

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

const int N = 1e5 + 5; 

int n, d; 
int start; 
int st, en; 
long long ans; 
int s[N], id[N];
pair<int, long long> seg[N * 2]; 

pair<int, long long> merge(pair<int, long long> x, pair<int, long long> y) {
  return make_pair(x.first + y.first, x.second + y.second); 
}

void upd(int nd, int l, int r, int p, int v) {
  if (l == r) {
    seg[nd].first += v; 
    seg[nd].second += v * s[l];
    return;
  }
  int mid = (l + r) / 2;
  int rs = nd + ((mid - l + 1) << 1); 
  if (p <= mid) {
    upd(nd + 1, l, mid, p, v);
  } else {
    upd(rs, mid + 1, r, p, v); 
  }
  seg[nd] = merge(seg[nd + 1], seg[rs]); 
} 

long long dive(int nd, int l, int r, int k) {
  if (l == r) {
    return (long long) min(k, seg[nd].first) * s[l]; 
  }
  int mid = (l + r) / 2;
  int rs = nd + ((mid - l + 1) << 1);
  if (seg[rs].first >= k) {
    return dive(rs, mid + 1, r, k); 
  }
  return dive(nd + 1, l, mid, k - seg[rs].first) + seg[rs].second; 
}

void edit(int l, int r) {
  while (st > l) upd(0, 0, n - 1, id[--st], 1);
  while (en < r) upd(0, 0, n - 1, id[++en], 1);
  while (st < l) upd(0, 0, n - 1, id[st++], -1); 
  while (en > r) upd(0, 0, n - 1, id[en--], -1); 
}

void solve(int l, int r, int optl, int optr) {
  if (l > r) return; 
  int mid = (l + r) / 2; 
  if (mid > start) {
    return solve(l, mid - 1, optl, optr); 
  }
  pair<long long, int> opt; 
  for (int i = max(optl, mid); i <= optr; ++i) {
    edit(mid, i); 
    if (i >= start) {
      int rem = max(0, d - (i - mid + min(i - start, start - mid)));
      opt = max(opt, make_pair(dive(0, 0, n - 1, rem), i)); 
    }
  }
  ans = max(ans, opt.first); 
  solve(l, mid - 1, optl, opt.second);
  solve(mid + 1, r, opt.second, optr); 
}

long long int findMaxAttraction(int n_, int start_, int d_, int attraction[]) {
  n = n_; d = d_;
  start = start_; 
  for (int i = 0; i < n; ++i) {
    s[i] = attraction[i];
  }
  sort(s, s + n);
  for (int i = 0; i < n; ++i) {
    id[i] = lower_bound(s, s + n, attraction[i]) - s; 
  }
  st = 1, en = 0; 
  solve(0, n - 1, 0, n - 1); 
  return ans;
}

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