Submission #920851

#	Time	Username	Problem	Language	Result	Execution time	Memory
920851		rxlfd314	Holiday (IOI14_holiday)	C++17	7 / 100	73 ms	65536 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using arl2 = array<ll, 2>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

constexpr int mxN = 100001;
int N, D, start;

struct Node {
  ll val;
  int cnt;
  Node *lft, *rht;
  Node() : val(0), cnt(0), lft(nullptr), rht(nullptr) {}
  Node(ll v, int c) : val(v), cnt(c), lft(nullptr), rht(nullptr) {}
  Node(Node *n) : val(n->val), cnt(n->cnt), lft(n->lft), rht(n->rht) {}
  Node(Node *l, Node *r) {
    val = (l ? l->val : 0ll) + (r ? r->val : 0ll);
    cnt = (l ? l->cnt : 0) + (r ? r->cnt : 0);
    lft = l, rht = r;
  }
};

Node *sts[mxN];
Node *build(int tl = 0, int tr = N) {
  if (tl == tr)
    return new Node();
  int tm = tl + tr >> 1;
  return new Node(build(tl, tm), build(tm+1, tr));
}

Node *upd(Node *n, int p, int v, int tl = 0, int tr = N) {
  if (tl == tr)
    return new Node(v, 1);
  int tm = tl + tr >> 1;
  if (p <= tm)
    return new Node(upd(n->lft, p, v, tl, tm), n->rht);
  return new Node(n->lft, upd(n->rht, p, v, tm+1, tr));
}

ll qry(Node *l, Node *r, int k, int tl = 0, int tr = N) {
  if (tl == tr)
    return k ? r->val - l->val : 0;
  int tm = tl + tr >> 1;
  if (r->rht->cnt - l->rht->cnt <= k)
    return r->rht->val - l->rht->val + qry(l->lft, r->lft, k - r->rht->cnt + l->rht->cnt, tl, tm);
  return qry(l->rht, r->rht, k, tm+1, tr);
}

ll ans;
void dnc(int tl, int tr, int optl_ltr, int optr_ltr, int optl_rtl, int optr_rtl) {
  if (tr < tl)
    return;
  int tm = tl + tr >> 1;
  
  arl2 best_ltr = {0, 0};
  FOR(i, max(1, optl_ltr), optr_ltr)
    if (start + tm - 2 * i < D)
      best_ltr = max(best_ltr, arl2{qry(sts[i-1], sts[tm], D - start - tm + 2 * i), i});

  arl2 best_rtl = {0, 0};
  FOR(i, max(1, optl_rtl), optr_rtl)
    if (2 * tm - start - i < D)
      best_rtl = max(best_rtl, arl2{qry(sts[i-1], sts[tm], D - 2 * tm + start + i), i});
  
  //cout << "answer for " << tm << ": " << max(best_ltr[0], best_rtl[0]) << ' ' << max(best_ltr, best_rtl)[1] << '\n';
  
  ans = max({ans, best_ltr[0], best_rtl[0]});
  dnc(tl, tm - 1, optl_ltr, best_ltr[1], optl_rtl, best_rtl[1]);
  dnc(tm + 1, tr, best_ltr[1], optr_ltr, best_rtl[1], optr_rtl);
}

ll findMaxAttraction(int _N, int _start, int _D, int *YEET) {
  N = _N;
  D = _D;
  start = _start + 1;
  vt<int> A(N+1);
  FOR(i, 0, N-1)
    A[i+1] = YEET[i];

  vt<ari2> cmp;
  FOR(i, 1, N)
    cmp.push_back({A[i], i});
  sort(all(cmp));
  auto ind = [&](ari2 v) {
    return lower_bound(all(cmp), v) - begin(cmp);
  };

  sts[0] = new Node(build());
  FOR(i, 1, N) {
    sts[i] = new Node(sts[i-1]);
    sts[i] = new Node(upd(sts[i], ind({A[i], i}), A[i]));
  }

  dnc(start, N, 1, start, 1, start);
  return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'Node* build(int, int)':
holiday.cpp:37:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
holiday.cpp: In function 'Node* upd(Node*, int, int, int, int)':
holiday.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
holiday.cpp: In function 'll qry(Node*, Node*, int, int, int)':
holiday.cpp:53:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
holiday.cpp: In function 'void dnc(int, int, int, int, int, int)':
holiday.cpp:63:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |   int tm = tl + tr >> 1;
      |            ~~~^~~~

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