oj.uz

Submission #418754

# Submission time Handle Problem Language Result Execution time Memory
418754 2021-06-05T19:56:24 Z Hegdahl Dancing Elephants (IOI11_elephants) C++17
100 / 100
 8079 ms 13304 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "elephants.h"
#define ar array
using namespace std;

const int mxN = 15e4;
int n, l, R, a[mxN], idxs[mxN], where[mxN];

struct Chunk {
  int size;
  vector<int> xs;
  vector<ar<int, 2>> dp;

  Chunk(vector<int> &&_xs) : size((int)_xs.size()), xs(move(_xs)) {
    dp.resize(size);
    recalc(size-1);
  }

  void recalc(int from) {
    for (int i = from; i >= 0; --i) {
      int j = lower_bound(xs.begin(), xs.end(), xs[i]+l) - xs.begin();
      if (j == size) dp[i] = {1, xs[i]+l};
      else dp[i] = {dp[j][0]+1, dp[j][1]};
    }
  }

  void insert(int x) {
    ++size;
    int i = int(upper_bound(xs.begin(), xs.end(), x) - xs.begin());
    xs.insert(xs.begin()+i, x);
    dp.insert(dp.begin()+i, {0, 0});
    recalc(i);
  }

  void erase(int x) {
    --size;
    int i = int(lower_bound(xs.begin(), xs.end(), x) - xs.begin());
    dp.erase(dp.begin() + i);
    xs.erase(xs.begin() + i);
    recalc(i-1);
  }

  ar<int, 2> qry(int x) {
    int j = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
    if (j == size) return {0, x};
    return dp[j];
  }
};

vector<Chunk> chunks;

void recalc() {
  iota(idxs, idxs+n, 0);
  sort(idxs, idxs+n, [&](int i, int j){ return a[i] < a[j]; });

  chunks.clear();
  for (int i0 = 0; i0 < n; i0 += R) {
    vector<int> xs;
    for (int i = i0; i < min(i0+R, n); ++i) {
      xs.push_back(a[idxs[i]]);
      where[idxs[i]] = (int)chunks.size();
    }
    chunks.emplace_back(move(xs));
  }
}

void init(int N, int L, int X[]) {
  n = N, l = L+1;
  for (int i = 0; i < n; ++i)
    a[i] = X[i];

  R = sqrt(2*N);

  recalc();
}

int solve() {
  int x = -1e9-10, ans = 0;

  for (int c = 0; c < (int)chunks.size(); ++c) {
    auto [used, new_x] = chunks[c].qry(x);
    ans += used;
    x = new_x;
  }

  return ans;
}

int update(int i, int y) {
  static int update_cnt = 0;
  if (++update_cnt%(2*R) == 0) {
    a[i] = y;
    recalc();
  } else {
    int c = where[i];
    chunks[c].erase(a[i]);

    a[i] = y;

    for (c = 1; c < (int)chunks.size(); ++c)
      if (chunks[c].size && chunks[c].xs[0] > a[i]) break;
    --c;
    chunks[c].insert(a[i]);
    where[i] = c;
  }

  return solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 416 ms 2072 KB Output is correct
8 Correct 495 ms 2116 KB Output is correct
9 Correct 811 ms 3264 KB Output is correct
10 Correct 945 ms 3264 KB Output is correct
11 Correct 1067 ms 3316 KB Output is correct
12 Correct 1300 ms 3820 KB Output is correct
13 Correct 961 ms 3316 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 416 ms 2072 KB Output is correct
8 Correct 495 ms 2116 KB Output is correct
9 Correct 811 ms 3264 KB Output is correct
10 Correct 945 ms 3264 KB Output is correct
11 Correct 1067 ms 3316 KB Output is correct
12 Correct 1300 ms 3820 KB Output is correct
13 Correct 961 ms 3316 KB Output is correct
14 Correct 584 ms 2728 KB Output is correct
15 Correct 881 ms 2628 KB Output is correct
16 Correct 1886 ms 4180 KB Output is correct
17 Correct 2224 ms 4844 KB Output is correct
18 Correct 2240 ms 4804 KB Output is correct
19 Correct 1171 ms 4056 KB Output is correct
20 Correct 2220 ms 5072 KB Output is correct
21 Correct 2173 ms 4760 KB Output is correct
22 Correct 1587 ms 4012 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 416 ms 2072 KB Output is correct
8 Correct 495 ms 2116 KB Output is correct
9 Correct 811 ms 3264 KB Output is correct
10 Correct 945 ms 3264 KB Output is correct
11 Correct 1067 ms 3316 KB Output is correct
12 Correct 1300 ms 3820 KB Output is correct
13 Correct 961 ms 3316 KB Output is correct
14 Correct 584 ms 2728 KB Output is correct
15 Correct 881 ms 2628 KB Output is correct
16 Correct 1886 ms 4180 KB Output is correct
17 Correct 2224 ms 4844 KB Output is correct
18 Correct 2240 ms 4804 KB Output is correct
19 Correct 1171 ms 4056 KB Output is correct
20 Correct 2220 ms 5072 KB Output is correct
21 Correct 2173 ms 4760 KB Output is correct
22 Correct 1587 ms 4012 KB Output is correct
23 Correct 5897 ms 7596 KB Output is correct
24 Correct 6080 ms 7780 KB Output is correct
25 Correct 4942 ms 7656 KB Output is correct
26 Correct 7298 ms 7620 KB Output is correct
27 Correct 4504 ms 7512 KB Output is correct
28 Correct 950 ms 3140 KB Output is correct
29 Correct 905 ms 2936 KB Output is correct
30 Correct 962 ms 2920 KB Output is correct
31 Correct 894 ms 3076 KB Output is correct
32 Correct 6883 ms 7800 KB Output is correct
33 Correct 6194 ms 7740 KB Output is correct
34 Correct 6257 ms 7636 KB Output is correct
35 Correct 3434 ms 7492 KB Output is correct
36 Correct 2572 ms 7768 KB Output is correct
37 Correct 8079 ms 9172 KB Output is correct
38 Correct 6119 ms 10744 KB Output is correct
39 Correct 4124 ms 11580 KB Output is correct
40 Correct 5793 ms 10676 KB Output is correct
41 Correct 7463 ms 13096 KB Output is correct
42 Correct 7473 ms 13304 KB Output is correct