Submission #555290

#	Time	Username	Problem	Language	Result	Execution time	Memory
555290		Soumya1	Holiday (IOI14_holiday)	C++17	100 / 100	702 ms	5868 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e5 + 5;
int a[mxN], val[mxN];
int n, d, start;
long long t[4 * mxN];
int cnt[4 * mxN];
long long ans = 0;
int lptr = 1, rptr = 1;
void update(int x, int lx, int rx, int i, int del) {
  if (lx == rx) {
    t[x] += del * val[lx];
    cnt[x] += del;
    return;
  }
  int mx = (lx + rx) >> 1;
  if (i <= mx) update(x << 1, lx, mx, i, del);
  else update(x << 1 | 1, mx + 1, rx, i, del);
  t[x] = t[x << 1] + t[x << 1 | 1];
  cnt[x] = cnt[x << 1] + cnt[x << 1 | 1];
}
long long query(int x, int lx, int rx, int take) {
  if (lx == rx) return 1LL * val[lx] * min(cnt[x], take);
  int mx = (lx + rx) >> 1;
  if (cnt[x << 1 | 1] >= take) return query(x << 1 | 1, mx + 1, rx, take);
  return t[x << 1 | 1] + query(x << 1, lx, mx, take - cnt[x << 1 | 1]);
}
void move_ptr(int l, int r) {
  while (lptr > l) update(1, 1, n, a[--lptr], 1);
  while (rptr < r) update(1, 1, n, a[++rptr], 1);
  while (rptr > r) update(1, 1, n, a[rptr--], -1);
  while (lptr < l) update(1, 1, n, a[lptr++], -1);
}
void solve(int l, int r, int optl, int optr) {
  if (l > r) return;
  int m = (l + r) >> 1;
  int opt;
  long long best = -1;
  for (int i = optl; i <= min(optr, m); i++) {
    int can_take = d - (m - i) - min(abs(start - i), abs(start - m));
    can_take = max(can_take, 0);
    move_ptr(i, m);
    long long cost = query(1, 1, n, can_take);
    if (best < cost) {
      best = cost;
      opt = i;
    }
  }
  ans = max(ans, best);
  solve(l, m - 1, optl, opt);
  solve(m + 1, r, opt, optr);
}
long long int findMaxAttraction(int _n, int _start, int _d, int attraction[]) {
  n = _n, start = _start + 1, d = _d;
  int _attraction[n];
  for (int i = 0; i < n; i++) _attraction[i] = attraction[i];
  sort(_attraction, _attraction + n);
  for (int i = 0; i < n; i++) val[i + 1] = _attraction[i];
  for (int i = 1; i <= n; i++) a[i] = 1 + lower_bound(_attraction, _attraction + n, attraction[i - 1]) - _attraction;
  update(1, 1, n, a[1], 1);
  solve(1, n, 1, n);
  return ans;
  return 0;
}

Compilation message (stderr)

holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:51:8: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |   solve(l, m - 1, optl, opt);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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