oj.uz

Submission #555290

# Submission time Handle Problem Language Result Execution time Memory
555290 2022-04-30T11:17:41 Z Soumya1 Holiday (IOI14_holiday) C++17
100 / 100
 702 ms 5868 KB 
#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

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.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 2132 KB Output is correct
2 Correct 378 ms 2132 KB Output is correct
3 Correct 374 ms 2132 KB Output is correct
4 Correct 382 ms 2116 KB Output is correct
5 Correct 520 ms 3788 KB Output is correct
6 Correct 125 ms 1820 KB Output is correct
7 Correct 258 ms 2700 KB Output is correct
8 Correct 324 ms 2984 KB Output is correct
9 Correct 89 ms 1552 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 852 KB Output is correct
2 Correct 7 ms 708 KB Output is correct
3 Correct 10 ms 852 KB Output is correct
4 Correct 11 ms 852 KB Output is correct
5 Correct 10 ms 836 KB Output is correct
6 Correct 3 ms 712 KB Output is correct
7 Correct 3 ms 700 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 3 ms 724 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 2804 KB Output is correct
2 Correct 446 ms 5868 KB Output is correct
3 Correct 261 ms 3156 KB Output is correct
4 Correct 10 ms 852 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 3 ms 692 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 702 ms 5752 KB Output is correct
9 Correct 697 ms 5756 KB Output is correct