Submission #555612

#	Time	Username	Problem	Language	Result	Execution time	Memory
555612		MilosMilutinovic	Holiday (IOI14_holiday)	C++14	100 / 100	623 ms	13740 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX = 500000;

int n, s, a[MAX], cc[4 * MAX], ord[MAX], id[MAX], tl, tr;
long long sum[4 * MAX], dL[MAX], dl[MAX], dR[MAX], dr[MAX];

void modify(int node, int l, int r, int i, int x, int v) {
  cc[node] += x;
  sum[node] += v;
  if (l == r) {
    return;
  }
  int mid = l + r >> 1;
  if (i <= mid) {
    modify(node + node, l, mid, i, x, v);
  } else {
    modify(node + node + 1, mid + 1, r, i, x, v);
  }
}

long long walk(int node, int l, int r, int x) {
  if (l == r) {
    return (x >= 1 ? sum[node] : 0LL);
  }
  int mid = l + r >> 1;
  if (cc[node + node + 1] >= x) {
    return walk(node + node + 1, mid + 1, r, x);
  } else {
    return sum[node + node + 1] + walk(node + node, l, mid, x - cc[node + node + 1]);
  }
}

void fixL(int l) {
  while (tl > l) {
    --tl;
    modify(1, 0, n - 1, id[tl], 1, a[tl]);
  }
  while (tl < l) {
//    cout << "brisem " << tl << '\n';
    modify(1, 0, n - 1, id[tl], -1, -a[tl]);
    tl++;
  }
}

void fixR(int r) {
  while (tr < r) {
    tr++;
//    cout << "addujem " << tr << '\n';
    modify(1, 0, n - 1, id[tr], 1, a[tr]);
  }
  while (tr > r) {
    modify(1, 0, n - 1, id[tr], -1, -a[tr]);
    tr--;
  }
}

long long get(int L, int R, int x) {
  fixL(L);
  fixR(R);
  return walk(1, 0, n - 1, x);
}

void solveL(int l, int r, int ll, int rr, int dc, long long* c) {
  if (l > r) {
    return;
  }
  int mid = l + r >> 1;
  int opt = rr;
  long long mx = -1;
  for (int i = rr; i >= ll; i--) {
    if ((s - i) * dc > mid) {
      continue;
    }
    long long cur = get(i, s - (dc == 1), mid - (s - i) * dc);
    if (mx < cur) {
      mx = cur;
      opt = i;
    }
  }
  c[mid] = mx;
  solveL(l, mid - 1, opt, rr, dc, c);
  solveL(mid + 1, r, ll, opt, dc, c);
}

void solveR(int l, int r, int ll, int rr, int dc, long long* c) {
  if (l > r) {
    return;
  }
  int mid = l + r >> 1;
  int opt = ll;
  long long mx = -1;
  for (int i = ll; i <= rr; i++) {
    if ((i - s) * dc > mid) {
      continue;
    }
    long long cur = get(s + (dc == 1), i, mid - (i - s) * dc);
    if (mx < cur) {
      mx = cur;
      opt = i;
    }
  }
  c[mid] = mx;
  solveR(l, mid - 1, ll, opt, dc, c);
  solveR(mid + 1, r, opt, rr, dc, c);
}

long long findMaxAttraction(int N, int start, int d, int attraction[]) {
  n = N;
  s = start;
  for (int i = 0; i < n; i++) {
    a[i] = attraction[i];
    ord[i] = i;
  }
  sort(ord, ord + n, [&](int i, int j) {
    return a[i] < a[j];
  });
  for (int i = 0; i < n; i++) {
    id[ord[i]] = i;
  }
  tr = -1, tl = 0;
  solveL(0, d, 0, s, 2, dL);
  solveL(0, d, 0, s, 1, dl);
  solveR(0, d, s, n - 1, 2, dR);
  solveR(0, d, s, n - 1, 1, dr);
  long long ans = max(dl[d], dr[d]);
  for (int i = 0; i <= d; i++) {
    ans = max(ans, dL[i] + dr[d - i]);
    ans = max(ans, dl[i] + dR[d - i]);
  }
  return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void modify(int, int, int, int, int, int)':
holiday.cpp:17:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |   int mid = l + r >> 1;
      |             ~~^~~
holiday.cpp: In function 'long long int walk(int, int, int, int)':
holiday.cpp:29:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   int mid = l + r >> 1;
      |             ~~^~~
holiday.cpp: In function 'void solveL(int, int, int, int, int, long long int*)':
holiday.cpp:71:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |   int mid = l + r >> 1;
      |             ~~^~~
holiday.cpp: In function 'void solveR(int, int, int, int, int, long long int*)':
holiday.cpp:93:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |   int mid = l + r >> 1;
      |             ~~^~~

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