Submission #1174859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174859		zNatsumi	Holiday (IOI14_holiday)	C++20	30 / 100	43 ms	35596 KiB

holiday

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e5 + 5;

int n, st, d, a[N], lim;
vector<int> rrh;

namespace PIT{
  struct node{
    node *l, *r;
    int cnt = 0;
    ll sum = 0;

    node(node *l, node *r): l(l), r(r), cnt(0), sum(0LL){
      if(l) cnt += l->cnt, sum += l->sum;
      if(r) cnt += r->cnt, sum += r->sum;
    }
    node(int a, ll b): l(NULL), r(NULL), cnt(a), sum(b){}
  };

  node* ver[N];
  int id = 0;

  node* build(int tl, int tr){
    if(tl == tr) return new node(0, 0LL);
    int tm = tl + tr >> 1;
    return new node(build(tl, tm), build(tm + 1, tr));
  }
  node* upd(int pos, int x, int y, int tl, int tr, node* i){
    if(tl == tr) return new node(i->cnt + x, i->sum + y);

    int tm = tl + tr >> 1;
    if(pos <= tm) return new node(upd(pos, x, y, tl, tm, i->l), i->r);
    else return new node(i->l, upd(pos, x, y, tm + 1, tr, i->r));
  }
  ll get(int k, int tl, int tr, node* le, node* ri){
    if(tl == tr) return rrh[tl] * min(k, ri->cnt - le->cnt);
    int tm = tl + tr >> 1;


    if(ri->r->cnt - le->r->cnt >= k) return get(k, tm + 1, tr, le->r, ri->r);
    else return get(k - (ri->r->cnt - le->r->cnt), tl, tm, le->l, ri->l) + (ri->r->sum - le->r->sum);
  }
  void init(int tl, int tr){
    ver[0] = build(tl, tr);
  }
  void update(int pos, int x, int y, int tl, int tr){
    id += 1;
    ver[id] = upd(pos, x, y, tl, tr, ver[id - 1]);
  }
  ll get_k(int k, int tl, int tr, int le, int ri){
    return get(k, tl, tr, ver[le - 1], ver[ri]);
  }
}

long long findMaxAttraction(int _n, int _st, int _d, int _a[]){
  n = _n; st = _st + 1; d = _d;
  for(int i = 1; i <= n; i++) a[i] = _a[i - 1];

  for(int i = 1; i <= n; i++) rrh.push_back(a[i]);
  sort(rrh.begin(), rrh.end());
  rrh.erase(unique(rrh.begin(), rrh.end()), rrh.end());

  lim = rrh.size() - 1;
  for(int i = 1; i <= n; i++) a[i] = lower_bound(rrh.begin(), rrh.end(), a[i]) - rrh.begin();

  PIT::init(0, lim);
  for(int i = 1; i <= n; i++) PIT::update(a[i], 1, rrh[a[i]], 0, lim);

  ll res = 0;
  for(int l = 1; l <= st; l++){
    for(int r = st; r <= n; r++){
      int tmp = min(r + st - 2*l, 2*r - st - l);
      if(tmp >= d) break;
      res = max(res, PIT::get_k(min(d - tmp, r - l + 1), 0, lim, l, r));
    }
  }
  return res;
}

//#define zNatsumi
#ifdef zNatsumi

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
  #define task "test"
  if(fopen(task ".inp", "r")){
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);
  }
  int n, st, d, a[N];
  cin >> n >> st >> d;
  for(int i = 0; i < n; i++) cin >> a[i];
  cout << findMaxAttraction(n, st, d, a);
}
#endif

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