Submission #990402

#	Time	Username	Problem	Language	Result	Execution time	Memory
990402		jklepec	Holiday (IOI14_holiday)	C++11	100 / 100	749 ms	22324 KiB

holiday

#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<

typedef long long ll;
typedef pair<int, ll> point;

const int MAXN = 1e5 + 5, off = 1 << 17, MAX = 3e5 + 5;

int S;

int a[MAXN], convert[MAXN];
point T[2 * off];

ll ans[MAX + 5][3][2];

#define qunatity first
#define sum second

point operator +(const point &A, const point &B) {
  point ret;
  ret.qunatity = A.qunatity + B.qunatity;
  ret.sum = A.sum + B.sum;
  return ret;
}

void shine(int i) {
  i = convert[i];

  i += off;
  assert(T[i].qunatity == 0);

  T[i].qunatity = 1;
  T[i].sum = a[i - off];

  for(i /= 2; i; i /= 2) {
    T[i] = T[i * 2] + T[i * 2 + 1];
  }
}
void fade(int i) {
  i = convert[i];

  i += off;
  assert(T[i].qunatity == 1);

  T[i].qunatity = 0;
  T[i].sum = 0;

  for(i /= 2; i; i /= 2) {
    T[i] = T[i * 2] + T[i * 2 + 1];
  }
}

ll query(int k, int x = 1) {
  if(T[x].qunatity <= k) {
    return T[x].sum;
  }
  if(x >= off) {
    return 0;
  }
  if(T[x * 2 + 1].qunatity <= k) {
    return query(k - T[x * 2 + 1].qunatity, x * 2) + T[x * 2 + 1].sum;
  }
  return query(k, x * 2 + 1);
}

void calc(int lo, int hi, int from, int to, int mul, int heading) {
  if(lo > hi) return;

  int mid = (lo + hi) >> 1;

  int pivot = from; ll best = 0;
  int d = from < to ? 1 : -1;

  for(int i = from; i != to + d; i += d) {
    shine(i);
    ll value = query(mid - abs(S - i) * mul);

    if(value > best) {
      pivot = i;
      best = value;
    }
  }

  ans[mid][mul][heading] = best;

  for(int i = pivot; i != to + d; i += d) {
    fade(i);
  }

  calc(mid + 1, hi, pivot, to, mul, heading);

  for(int i = from; i != pivot; i += d) {
    fade(i);
  }

  calc(lo, mid - 1, from, pivot, mul, heading);
}

ll findMaxAttraction(int n, int s, int d, int attraction[]) {

  memset(ans, 0, sizeof ans);

  vector<point> v;
  REP(i, n) {
    a[i] = attraction[i];
    v.push_back({a[i], i});
  }

  sort(v.begin(), v.end());
  REP(i, n) {
    convert[v[i].second] = i;
  }
  sort(a, a + n);

  S = s;
  if(s < n - 1) {
    calc(2, MAX, s + 1, n - 1, 1, 1);
    calc(3, MAX, s + 1, n - 1, 2, 1);
  }

  if(s) {
    calc(2, MAX, s - 1, 0, 1, 0);
    calc(3, MAX, s - 1, 0, 2, 0);
  }

  int addition = 0; ll sol = 0;
  REP(k, 2) {
    REP(dd, d + 1 - k) {
      sol = max(sol, ans[dd][2][1] + ans[d - dd - k][1][0] + addition);
      sol = max(sol, ans[dd][2][0] + ans[d - dd - k][1][1] + addition);
    }
    addition += a[convert[s]];
  }

  return sol;
}

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