Submission #1043931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043931		Hydrolyzed	Holiday (IOI14_holiday)	C++17	0 / 100	60 ms	65536 KiB

holiday

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

using namespace std;
using ll = long long;

const int MxN = 100010;

struct node_t;
using pnode_t = node_t *;

struct node_t {
  ll v;
  int cnt;
  pnode_t l, r;
  node_t(ll _v=0ll, int _cnt=0):
    v(_v), cnt(_cnt), l(nullptr), r(nullptr) {}
  friend node_t operator + (const node_t &lhs, const node_t &rhs) {
    return node_t(lhs.v + rhs.v, lhs.cnt + rhs.cnt);
  }
};

struct interval_t {
  ll v;
  int l, r;
  interval_t(ll _v):
    v(_v), l(0), r(0) {}
};

int n, stp, days;
ll a[MxN];
pnode_t roots[MxN];

namespace persistent {
  void build(int l, int r, pnode_t &cur) {
    cur = new node_t();
    if(l == r) {
      cur->v = 0ll;
      cur->cnt = 0ll;
      return ;
    }
    int mid = (l + r) >> 1;
    build(l, mid, cur->l);
    build(mid + 1, r, cur->r);
    cur->v = cur->l->v + cur->r->v;
    cur->cnt = cur->l->cnt + cur->r->cnt;
  }
  void update(int l, int r, int id, node_t val, pnode_t &cur, pnode_t pre) {
    cur = new node_t(*pre);
#ifdef ICY
    cerr << "UPDATING: " << l << " " << r << "\n";
#endif
    if(l == r) {
      cur->v = val.v;
      cur->cnt = 1;
      return ;
    }
    int mid = (l + r) >> 1;
    if(id <= mid) {
      update(l, mid, id, val, cur->l, pre->l);
    }
    else {
      update(mid + 1, r, id, val, cur->r, pre->r);
    }
#ifdef ICY
    cerr << "RANGE: [" << l << ", " << r << "]\n";  
    cerr << "AFTER UPDATED: L(" << (cur->l == nullptr ? "NULL" : "HAVE!") << "), R(" << (cur->r == nullptr ? "NULL" : "HAVE!") << ")\n";
#endif
    cur->v = cur->l->v + cur->r->v;
    cur->cnt = cur->l->cnt + cur->r->cnt;
  }
  ll calc(int l, int r, pnode_t old_ver, pnode_t new_ver, ll x) {
#ifdef ICY
    assert(old_ver != nullptr && "old_ver is null");
    assert(new_ver != nullptr && "new_ver is null");
    cerr << "IN PERSIST: " << l << " " << r << "\n";
#endif
    if(l > r) {
      return 0ll;
    }
    if(l == r) {
      if(x <= 0ll) {
        return 0ll;
      }
      if(new_ver->cnt - old_ver->cnt <= x) {
        return new_ver->v - old_ver->v;
      }
    }
#ifdef ICY
    cerr << "GOING SOMEWHERE" << "\n";
    assert(old_ver->r != nullptr && "old_ver is null");
    assert(new_ver->r != nullptr && "new_ver is null");
#endif
    int mid = (l + r) >> 1;
    ll right_count = new_ver->r->cnt - old_ver->r->cnt;
#ifdef ICY
    cerr << "RIGHT COUNT: " << right_count << "\n";
#endif
    if(right_count >= x) {
#ifdef ICY
      cerr << "GO LEFT\n";
#endif
      return calc(l, mid, old_ver->l, new_ver->l, x);
    }
#ifdef ICY
    cerr << "GO RIGHT\n";
#endif
    return new_ver->r->v - old_ver->r->v + calc(mid + 1, r, old_ver->r, new_ver->r, x - right_count);
  }
}

ll divide(int l, int r, int opt_l, int opt_r) {
  if(l > r) {
    return 0ll;
  }
  int mid = (l + r) >> 1;
  ll res = 0ll;
  interval_t best(0ll);
  for(int k=opt_l; k<=opt_r; ++k) {
    int needs = mid - k + min(stp - k, mid - stp);
    if(needs > days) {
      continue;
    }
#ifdef ICY
    cerr << "ASKING: " << days - needs + 1 << " " << k << "[" << n << "]\n";
#endif
    ll cur_answer = persistent::calc(1, n, roots[k], roots[mid], days - needs + 1);
#ifdef ICY
    cerr << "DONE QUERY: " << cur_answer << "\n";
#endif
    if(best.v < cur_answer) {
      best.v = cur_answer;
      best.l = best.r = k;
    }
    else if(best.v == cur_answer) {
      best.r = k;
    }
  }
  res = max(res, divide(l, mid - 1, opt_l, best.r));
  res = max(res, divide(mid + 1, r, best.l, opt_r));
  return res;
}

long long findMaxAttraction(int n, int start, int d, int attraction[]) {
  stp = start + 1;
  days = d;
  ::n = n;
  vector<pair<ll, int>> c_a;
  for(int i=1; i<=n; ++i) {
    a[i] = (ll) attraction[i - 1];
    c_a.emplace_back(a[i], i);
  }
  sort(c_a.begin(), c_a.end());
  persistent::build(1, n, roots[0]);
  for(int i=1; i<=n; ++i) {
    int idx = upper_bound(c_a.begin(), c_a.end(), make_pair(a[i - 1], i)) - c_a.begin();
    persistent::update(1, n, idx, node_t(c_a[idx - 1].first, 1), roots[i], roots[i - 1]);
#ifdef ICY
    cerr << "ROOT(" << i << "): " << (roots[i] != nullptr ? "": "MISSING") << "\n";
#endif
  }
#ifdef ICY
  cerr << "DONE BUILDING!\n";
#endif
  ll answer = divide(start, n, 1, start - 1);
  return answer;
}

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