Submission #1001037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001037		abczz	Holiday (IOI14_holiday)	C++17	100 / 100	1469 ms	11344 KiB

holiday

//#include"holiday.h"
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <queue>
#define ll long long

using namespace std;

ll n, x, z, cl, cr, f, G[100000];
queue <array<ll, 4>> Q[2];
array <ll, 2> A[100000];

struct SegTree{
  vector <ll> st{vector <ll> (400000, 0)};
  vector <ll> cnt{vector <ll> (400000, 0)};
  void update(ll id, ll l, ll r, ll q, bool b) {
    if (l == r) {
      if (b) st[id] = A[l][0], cnt[id] = 1;
      else st[id] = cnt[id] = 0;
      return;
    }
    ll mid = (l+r)/2;
    if (q <= mid) update(id*2, l, mid, q, b);
    else update(id*2+1, mid+1, r, q, b);
    st[id] = st[id*2] + st[id*2+1];
    cnt[id] = cnt[id*2] + cnt[id*2+1];
  }
  ll k;
  ll init_query(ll K) {
    k = K;
    return kth_query(1, 0, n-1);
  }
  ll kth_query(ll id, ll l, ll r) {
    if (k >= cnt[id]) {
      k -= cnt[id];
      return st[id];
    }
    if (l == r) return 0;
    ll mid = (l+r)/2;
    if (cnt[id*2] >= k) return kth_query(id*2, l, mid);
    else {
      k -= cnt[id*2];
      return st[id*2] + kth_query(id*2+1, mid+1, r);
    }
  }
}ST;

ll solve(ll l, ll r, ll optL, ll optR) {
  ll mid = (l+r)/2;
  while (cl < mid) {
    ST.update(1, 0, n-1, G[cl], 0);
    ++cl;
  }
  cr = max(cr, mid);
  while (cr < optL) {
    ST.update(1, 0, n-1, G[cr], 1);
    ++cr;
  }
  ll opt = -1, optVal = -1, cur, m = z-(x-mid)-max(0LL, optL-mid);
  for (int i=max(mid, optL); i<=optR; ++i) {
    if (m <= 0) break;
    ST.update(1, 0, n-1, G[i], 1);
    cur = ST.init_query(m);
    if (cur >= optVal) {
      opt = i;
      optVal = cur;
    }
    --m;
  }
  for (int i=max(mid, optL); i<=optR; ++i) {
    ST.update(1, 0, n-1, G[i], 0);
  } 
  //cout << mid << " " << optVal << " " << opt << endl;
  if (l != mid) Q[1].push({l, mid-1, optL, opt});
  if (mid != r) Q[1].push({mid+1, r, opt, optR});
  return optVal;
}

void sharky() {
  Q[0].push({0, x, 0, n-1});
  while (!Q[0].empty()) {
    cl = cr = 0;
    while (!Q[0].empty()) {
      auto [l, r, ql, qr] = Q[0].front();
      Q[0].pop();
      f = max(f, solve(l, r, ql, qr));
    }
    swap(Q[0], Q[1]);
    while (cl < cr) {
      ST.update(1, 0, n-1, G[cl], 0);
      ++cl;
    }
  }
}

long long int findMaxAttraction(int _n, int start, int d, int attraction[]) {
  n = _n, x = start, z = d;
  for (int i=0; i<n; ++i) A[i] = {attraction[i], i};
  sort(A, A+n, [](auto a, auto b) {
    return a[0] > b[0];
  });
  for (int i=0; i<n; ++i) {
    G[A[i][1]] = i;
  }
  sharky();
  for (int i=0; i<n/2; ++i) {
    swap(G[i], G[n-1-i]);
  }
  x = n-1-x;
  sharky();
  return f;
}

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