제출 #313198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
313198		quocnguyen1012	휴가 (IOI14_holiday)	C++14	23 / 100	773 ms	6636 KiB

holiday

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;

template<class T>
bool chkmax(T & x, T v) {
  if (x < v) {
    x = v;
    return true;
  }
  return false;
}
ll res = 0;
int N, a[maxn], req;
int val[maxn], idx[maxn];
pair<ll, int> tr[4 * maxn];
int st;

#define lc id << 1
#define rc id << 1 | 1
void upd(int pos, int val, int v, int id = 1, int l = 0, int r = N - 1) {
  if (l == r) {
    if (v) tr[id] = mp(val, 1);
    else tr[id] = mp(0, 0);
    return;
  }
  int mid = (l + r) / 2;
  if (pos <= mid) upd(pos, val, v, lc, l, mid);
  else upd(pos, val, v, rc, mid + 1, r);
  tr[id] = mp(tr[lc].fi + tr[rc].fi, tr[lc].se + tr[rc].se);
}

ll k_largest(int req, int id = 1, int l = 0, int r = N - 1) {
  if (req <= 0) return 0;
  if (tr[id].se <= req) return tr[id].fi;
  int mid = (l + r) / 2;
  if (tr[rc].se >= req)
    return k_largest(req, rc, mid + 1, r);
  req -= tr[rc].se;
  return tr[rc].fi + k_largest(req, lc, l, mid);
}

void dnc(int l, int r, int opl, int opr) {

  //cerr << l << ' ' << r << ' ' << opl << ' ' << opr;
  if (l > r)
    return;
  int mid = (l + r) / 2;

  ll resmid = -1e18;
  int opmid = 0;

  for (int i = mid; i <= r; ++i)
    upd(idx[i], a[i], 1);

  for (int i = opl; i <= opr; ++i) {
    upd(idx[i], a[i], 1);
    int take = req - (2 * (i - st) + st - mid);


    if (chkmax(resmid, k_largest(take))) {
      opmid = i;
    }
  }

  res = max(res, resmid);

  for (int i = opmid + 1; i <= opr; ++i)
    upd(idx[i], a[i], 0);
  for (int i = l; i <= r; ++i)
    upd(idx[i], a[i], 0);

  dnc(mid + 1, r, opmid, opr);

  for (int i = mid; i <= r; ++i)
    upd(idx[i], a[i], 1);
  for (int i = opr; i >= opl; --i) {
    upd(idx[i], a[i], 0);
  }
  dnc(l, mid - 1, opl, opmid);

  for (int i = opl; i <= opr; ++i)
    upd(idx[i], a[i], 0);
  for (int i = mid; i <= r; ++i)
    upd(idx[i], a[i], 0);
}

void solve(int _st, int attraction[]) {
  for (int i = 0; i < N; ++i)
    upd(i, 0, 0);

  st = _st;
  for (int i = 0; i < N; ++i)
    a[i] = attraction[i];
  vector<ii> v;
  for (int i = 0; i < N; ++i)
    v.eb(a[i], i);
  sort(v.begin(), v.end());
  for (int i = 0; i < N; ++i)
    idx[v[i].se] = i;

  dnc(0, st, st, N - 1);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
  N = n;
  req = d;
  //solve(start, attraction);

  reverse(attraction, attraction + N);
  start = N - 1 - start;
  solve(start, attraction);
  return res;
}

#ifdef LOCAL
signed main(void) {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
  freopen("A.INP", "r", stdin);
  freopen("A.OUT", "w", stdout);
#endif // LOCAL
  int n, st, d;
  cin >> n >> st >> d;
  int a[n];
  for (int i = 0 ; i < n; ++i)
    cin >> a[i];
  cout << findMaxAttraction(n, st, d, a);
}
#endif // LOCAL

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