oj.uz

Submission #1001037

# Submission time Handle Problem Language Result Execution time Memory
1001037 2024-06-18T13:22:14 Z abczz Holiday (IOI14_holiday) C++17
100 / 100
 1469 ms 11344 KB 
//#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9052 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 3 ms 9052 KB Output is correct
4 Correct 3 ms 9168 KB Output is correct
5 Correct 3 ms 9304 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 10672 KB Output is correct
2 Correct 528 ms 10576 KB Output is correct
3 Correct 560 ms 10576 KB Output is correct
4 Correct 650 ms 10664 KB Output is correct
5 Correct 858 ms 10688 KB Output is correct
6 Correct 180 ms 9556 KB Output is correct
7 Correct 407 ms 9960 KB Output is correct
8 Correct 509 ms 10236 KB Output is correct
9 Correct 127 ms 9556 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 9052 KB Output is correct
2 Correct 11 ms 9192 KB Output is correct
3 Correct 10 ms 9180 KB Output is correct
4 Correct 22 ms 9252 KB Output is correct
5 Correct 19 ms 9052 KB Output is correct
6 Correct 7 ms 9052 KB Output is correct
7 Correct 6 ms 9052 KB Output is correct
8 Correct 7 ms 9052 KB Output is correct
9 Correct 7 ms 9052 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 11344 KB Output is correct
2 Correct 537 ms 11324 KB Output is correct
3 Correct 327 ms 10064 KB Output is correct
4 Correct 18 ms 9052 KB Output is correct
5 Correct 6 ms 9052 KB Output is correct
6 Correct 6 ms 9052 KB Output is correct
7 Correct 6 ms 9048 KB Output is correct
8 Correct 1459 ms 10776 KB Output is correct
9 Correct 1469 ms 10644 KB Output is correct