oj.uz

Submission #313207

# Submission time Handle Problem Language Result Execution time Memory
313207 2020-10-15T13:51:18 Z quocnguyen1012 Holiday (IOI14_holiday) C++14
100 / 100
 1370 ms 8392 KB 
#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) {
  if (req <= 0) return 0;
  if (tr[id].se <= req) return tr[id].fi;
  if (tr[rc].se >= req)
    return k_largest(req, rc);
  req -= tr[rc].se;
  return tr[rc].fi + k_largest(req, lc);
}

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 = opl; i <= opr; ++i)
    upd(idx[i], a[i], 0);
  dnc(l, mid - 1, opl, opmid);

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

  for (int i = opl; i < opmid; ++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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 7600 KB Output is correct
2 Correct 348 ms 7384 KB Output is correct
3 Correct 383 ms 7504 KB Output is correct
4 Correct 353 ms 7384 KB Output is correct
5 Correct 447 ms 7308 KB Output is correct
6 Correct 117 ms 2200 KB Output is correct
7 Correct 233 ms 3932 KB Output is correct
8 Correct 277 ms 4220 KB Output is correct
9 Correct 79 ms 2012 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 512 KB Output is correct
2 Correct 7 ms 640 KB Output is correct
3 Correct 7 ms 640 KB Output is correct
4 Correct 18 ms 640 KB Output is correct
5 Correct 16 ms 512 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 7460 KB Output is correct
2 Correct 380 ms 7756 KB Output is correct
3 Correct 453 ms 3996 KB Output is correct
4 Correct 15 ms 512 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 1370 ms 8392 KB Output is correct
9 Correct 1360 ms 8268 KB Output is correct