oj.uz

Submission #418743

# Submission time Handle Problem Language Result Execution time Memory
418743 2021-06-05T19:41:56 Z Hegdahl Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 6608 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)) {
    recalc();
  }

  void recalc() {
    dp.resize(size);
    for (int i = size-1; 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;
    auto it = upper_bound(xs.begin(), xs.end(), x);
    xs.insert(it, x);
    recalc();
  }

  void erase(int x) {
    --size;
    auto it = lower_bound(xs.begin(), xs.end(), x);
    assert(it != xs.end());
    xs.erase(it);
    recalc();
  }

  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 1 ms 332 KB Output is correct
2 Correct 0 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 0 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 0 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 638 ms 1264 KB Output is correct
8 Correct 758 ms 1480 KB Output is correct
9 Correct 1255 ms 2460 KB Output is correct
10 Correct 1237 ms 2372 KB Output is correct
11 Correct 1229 ms 2336 KB Output is correct
12 Correct 2370 ms 2704 KB Output is correct
13 Correct 1145 ms 2332 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 0 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 638 ms 1264 KB Output is correct
8 Correct 758 ms 1480 KB Output is correct
9 Correct 1255 ms 2460 KB Output is correct
10 Correct 1237 ms 2372 KB Output is correct
11 Correct 1229 ms 2336 KB Output is correct
12 Correct 2370 ms 2704 KB Output is correct
13 Correct 1145 ms 2332 KB Output is correct
14 Correct 1084 ms 1964 KB Output is correct
15 Correct 1357 ms 1872 KB Output is correct
16 Correct 3490 ms 3136 KB Output is correct
17 Correct 4212 ms 3972 KB Output is correct
18 Correct 4147 ms 3880 KB Output is correct
19 Correct 2832 ms 3400 KB Output is correct
20 Correct 4137 ms 4048 KB Output is correct
21 Correct 4043 ms 3952 KB Output is correct
22 Correct 1969 ms 3352 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 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 638 ms 1264 KB Output is correct
8 Correct 758 ms 1480 KB Output is correct
9 Correct 1255 ms 2460 KB Output is correct
10 Correct 1237 ms 2372 KB Output is correct
11 Correct 1229 ms 2336 KB Output is correct
12 Correct 2370 ms 2704 KB Output is correct
13 Correct 1145 ms 2332 KB Output is correct
14 Correct 1084 ms 1964 KB Output is correct
15 Correct 1357 ms 1872 KB Output is correct
16 Correct 3490 ms 3136 KB Output is correct
17 Correct 4212 ms 3972 KB Output is correct
18 Correct 4147 ms 3880 KB Output is correct
19 Correct 2832 ms 3400 KB Output is correct
20 Correct 4137 ms 4048 KB Output is correct
21 Correct 4043 ms 3952 KB Output is correct
22 Correct 1969 ms 3352 KB Output is correct
23 Execution timed out 9025 ms 6608 KB Time limit exceeded
24 Halted 0 ms 0 KB -