oj.uz

Submission #418748

# Submission time Handle Problem Language Result Execution time Memory
418748 2021-06-05T19:46:40 Z Hegdahl Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 12224 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(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%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 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 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 0 ms 332 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 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 0 ms 332 KB Output is correct
7 Correct 544 ms 1276 KB Output is correct
8 Correct 682 ms 1356 KB Output is correct
9 Correct 1091 ms 2332 KB Output is correct
10 Correct 1109 ms 2376 KB Output is correct
11 Correct 1187 ms 2252 KB Output is correct
12 Correct 2001 ms 2720 KB Output is correct
13 Correct 1107 ms 2336 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 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 0 ms 332 KB Output is correct
7 Correct 544 ms 1276 KB Output is correct
8 Correct 682 ms 1356 KB Output is correct
9 Correct 1091 ms 2332 KB Output is correct
10 Correct 1109 ms 2376 KB Output is correct
11 Correct 1187 ms 2252 KB Output is correct
12 Correct 2001 ms 2720 KB Output is correct
13 Correct 1107 ms 2336 KB Output is correct
14 Correct 922 ms 1888 KB Output is correct
15 Correct 1163 ms 1872 KB Output is correct
16 Correct 2931 ms 2992 KB Output is correct
17 Correct 3466 ms 3884 KB Output is correct
18 Correct 3517 ms 4012 KB Output is correct
19 Correct 1965 ms 3360 KB Output is correct
20 Correct 3478 ms 4108 KB Output is correct
21 Correct 3392 ms 3876 KB Output is correct
22 Correct 1886 ms 3340 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 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 0 ms 332 KB Output is correct
7 Correct 544 ms 1276 KB Output is correct
8 Correct 682 ms 1356 KB Output is correct
9 Correct 1091 ms 2332 KB Output is correct
10 Correct 1109 ms 2376 KB Output is correct
11 Correct 1187 ms 2252 KB Output is correct
12 Correct 2001 ms 2720 KB Output is correct
13 Correct 1107 ms 2336 KB Output is correct
14 Correct 922 ms 1888 KB Output is correct
15 Correct 1163 ms 1872 KB Output is correct
16 Correct 2931 ms 2992 KB Output is correct
17 Correct 3466 ms 3884 KB Output is correct
18 Correct 3517 ms 4012 KB Output is correct
19 Correct 1965 ms 3360 KB Output is correct
20 Correct 3478 ms 4108 KB Output is correct
21 Correct 3392 ms 3876 KB Output is correct
22 Correct 1886 ms 3340 KB Output is correct
23 Correct 7422 ms 6588 KB Output is correct
24 Correct 7967 ms 6796 KB Output is correct
25 Correct 6259 ms 6768 KB Output is correct
26 Correct 8881 ms 6936 KB Output is correct
27 Correct 7649 ms 6560 KB Output is correct
28 Correct 1500 ms 5300 KB Output is correct
29 Correct 1450 ms 5320 KB Output is correct
30 Correct 1507 ms 5316 KB Output is correct
31 Correct 1462 ms 5332 KB Output is correct
32 Correct 7884 ms 11316 KB Output is correct
33 Correct 7414 ms 10460 KB Output is correct
34 Correct 7316 ms 11384 KB Output is correct
35 Correct 5466 ms 11880 KB Output is correct
36 Correct 3766 ms 11004 KB Output is correct
37 Execution timed out 9062 ms 12224 KB Time limit exceeded
38 Halted 0 ms 0 KB -