oj.uz

Submission #418737

# Submission time Handle Problem Language Result Execution time Memory
418737 2021-06-05T19:36:30 Z Hegdahl Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 14056 KB 
#include <bits/stdc++.h>
#include "elephants.h"
#define ar array
using namespace std;
using ll = long long;

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

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

  Chunk(vector<ll> &&_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<ll, 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<ll> xs;
    for (int i = i0; i < min(i0+R, n); ++i) {
      xs.push_back(a[idxs[i]]);
      where[idxs[i]] = 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() {
  ll x = -1e9-10, ans = 0;

  for (int c = 0; c < 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 < 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();
}

Compilation message

elephants.cpp: In function 'int solve()':
elephants.cpp:79:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Chunk>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for (int c = 0; c < chunks.size(); ++c) {
      |                   ~~^~~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Chunk>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for (c = 1; c < chunks.size(); ++c)
      |                 ~~^~~~~~~~~~~~~~~

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 531 ms 2328 KB Output is correct
8 Correct 633 ms 2884 KB Output is correct
9 Correct 995 ms 4608 KB Output is correct
10 Correct 1145 ms 4388 KB Output is correct
11 Correct 1194 ms 4436 KB Output is correct
12 Correct 2119 ms 5140 KB Output is correct
13 Correct 1102 ms 4348 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 531 ms 2328 KB Output is correct
8 Correct 633 ms 2884 KB Output is correct
9 Correct 995 ms 4608 KB Output is correct
10 Correct 1145 ms 4388 KB Output is correct
11 Correct 1194 ms 4436 KB Output is correct
12 Correct 2119 ms 5140 KB Output is correct
13 Correct 1102 ms 4348 KB Output is correct
14 Correct 1035 ms 3880 KB Output is correct
15 Correct 1128 ms 3624 KB Output is correct
16 Correct 3126 ms 5972 KB Output is correct
17 Correct 3613 ms 7600 KB Output is correct
18 Correct 3634 ms 7792 KB Output is correct
19 Correct 2238 ms 6620 KB Output is correct
20 Correct 3538 ms 7836 KB Output is correct
21 Correct 3453 ms 7596 KB Output is correct
22 Correct 1823 ms 6084 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 531 ms 2328 KB Output is correct
8 Correct 633 ms 2884 KB Output is correct
9 Correct 995 ms 4608 KB Output is correct
10 Correct 1145 ms 4388 KB Output is correct
11 Correct 1194 ms 4436 KB Output is correct
12 Correct 2119 ms 5140 KB Output is correct
13 Correct 1102 ms 4348 KB Output is correct
14 Correct 1035 ms 3880 KB Output is correct
15 Correct 1128 ms 3624 KB Output is correct
16 Correct 3126 ms 5972 KB Output is correct
17 Correct 3613 ms 7600 KB Output is correct
18 Correct 3634 ms 7792 KB Output is correct
19 Correct 2238 ms 6620 KB Output is correct
20 Correct 3538 ms 7836 KB Output is correct
21 Correct 3453 ms 7596 KB Output is correct
22 Correct 1823 ms 6084 KB Output is correct
23 Correct 6996 ms 13796 KB Output is correct
24 Correct 7734 ms 13572 KB Output is correct
25 Correct 5547 ms 13660 KB Output is correct
26 Correct 8157 ms 14056 KB Output is correct
27 Execution timed out 9097 ms 13700 KB Time limit exceeded
28 Halted 0 ms 0 KB -