Submission #102832

#	Time	Username	Problem	Language	Result	Execution time	Memory
102832		wxh010910	Holiday (IOI14_holiday)	C++17	24 / 100	135 ms	66560 KiB

holiday

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

using namespace std;

class node {
 public:
  node* l;
  node* r;
  int cnt;
  long long sum;
};

node* insert(node* u, int l, int r, int p, int w) {
  node* v = new node();
  v->l = u->l;
  v->r = u->r;
  v->cnt = u->cnt + 1;
  v->sum = u->sum + w;
  if (l != r) {
    int y = (l + r) >> 1;
    if (p <= y) {
      v->l = insert(u->l, l, y, p, w);
    } else {
      v->r = insert(u->r, y + 1, r, p, w);
    }
  }
  return v;
}

long long query(node* v, node* u, int l, int r, int k) {
  if (l == r) {
    return v->sum - u->sum;
  } else {
    int y = (l + r) >> 1;
    if (v->r->cnt - u->r->cnt >= k) {
      return query(v->r, u->r, y + 1, r, k);
    } else {
      return query(v->l, u->l, l, y, k - (v->r->cnt - u->r->cnt)) + (v->r->sum - u->r->sum);
    }
  }
}

long long findMaxAttraction(int n, int start, int d, int attraction[]) {
  node* null = new node();
  null->l = null->r = null;
  null->cnt = null->sum = 0;
  vector<int> order(n);
  for (int i = 0; i < n; ++i) {
    order[i] = i;
  }
  sort(order.begin(), order.end(), [&](int a, int b) {
    return attraction[a] < attraction[b];
  });
  vector<int> pos_in_order(n);
  for (int i = 0; i < n; ++i) {
    pos_in_order[order[i]] = i;
  }
  vector<node*> roots(n + 1, null);
  for (int i = 0; i < n; ++i) {
    roots[i + 1] = insert(roots[i], 0, n - 1, pos_in_order[i], attraction[i]);
  }
  long long ans = 0;
  function<void(int, int, int, int)> solve = [&](int l, int r, int ll, int rr) {
    if (l > r) {
      return;
    }
    int mid = (l + r) >> 1, pos = -1;
    long long best = -1;
    for (int i = ll; i <= rr; ++i) {
      int cnt = d - (i - mid) - min(i - start, start - mid);
      if (cnt < 0) {
        break;
      }
      long long value = (i - mid + 1 <= cnt ? roots[i + 1]->sum - roots[mid]->sum : query(roots[i + 1], roots[mid], 0, n - 1, cnt));
      if (best < value) {
        best = value;
        pos = i;
      }
    }
    ans = max(ans, best);
    solve(l, mid - 1, ll, pos);
    solve(mid + 1, r, pos, rr);
  };
  solve(max(0, start - d + 1), start, start, min(n - 1, start + d - 1));
  return ans;
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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