oj.uz

Submission #854134

# Submission time Handle Problem Language Result Execution time Memory
854134 2023-09-26T08:17:31 Z rxlfd314 Dancing Elephants (IOI11_elephants) C++17
100 / 100
 8982 ms 27228 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;
 
#define vt vector
#define size(x) (int(x.size()))
#define all(x) begin(x), end(x)
 
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
 
#define chmax(a, b) a = a > (b) ? a : (b)
#define chmin(a, b) a = a < (b) ? a : (b)
 
static constexpr int mxN = 150005, B = 388;
static int N, L, pos[mxN];
static ari2 A[mxN];
static vt<array<int, 5>> blocks[B]; // position, index, next block, next index, value to add
static vt<ari2> endss;
 
void fix() {
  ROF(i, size(endss)-1, 1)
    if (endss[i] < endss[i-1])
      swap(endss[i], endss[i-1]);
}
 
static void upd(int b, bool added) {
  if (!size(blocks[b]))
    return;
  
  if (added)
    ROF(i, size(blocks[b])-1, 1)
      if (blocks[b][i][0] < blocks[b][i-1][0])
        swap(blocks[b][i], blocks[b][i-1]);
 
  endss.push_back({blocks[b].back()[0], b});
  fix();
 
  int j = size(blocks[b]) - 1;
  ROF(i, size(blocks[b])-1, 0) {
    if (blocks[b].back()[0] <= blocks[b][i][0] + L) {
      blocks[b][i][2] = blocks[b][i][3] = blocks[b][i][4] = B;
      continue;
    }
    while (blocks[b][j-1][0] > blocks[b][i][0] + L)
      j--;
    blocks[b][i] = {
      blocks[b][i][0], blocks[b][i][1], b, 
      blocks[b][j][2] == b ? blocks[b][j][3] : j, 
      blocks[b][j][2] == b ? blocks[b][j][4] + 1 : 1
    };
  }
}
 
static void recalc() {
  int cur = 0;
  FOR(i, 0, (N-1)/B)
    FOR(j, 0, size(blocks[i])-1)
      A[cur++] = {blocks[i][j][0], blocks[i][j][1]};
 
  FOR(i, 0, (N-1)/B) {
    blocks[i].clear();
    int n = min(N, (i+1)*B);
    FOR(j, i*B, n-1) {
      blocks[i].push_back({A[j][0], A[j][1], B, B, B});
      pos[A[j][1]] = i;
    }
  }
  
  endss.clear();
  ROF(b, (N-1)/B, 0)
    upd(b, false);
}
 
void init(int _N, int _L, int X[]) {
  N = _N, L = _L;
  FOR(i, 0, N-1)
    blocks[0].push_back({X[i], i, B, B, B});
  recalc();
}
 
static int it_cnt;
int update(int ind, int y) {
  int &p = pos[ind];
  FOR(i, 0, size(blocks[p])-1) {
    if (blocks[p][i][1] == ind) {
      if (i == size(blocks[p])-1) {
        endss.erase(find(all(endss), ari2{blocks[p][i][0], p}));
        if (i) {
          endss.push_back({blocks[p][i-1][0], p});
          fix();
        }
      }
      blocks[p].erase(begin(blocks[p]) + i);
      break;
    }
  }
 
  int it = lower_bound(all(endss), ari2{y, 0}) - begin(endss);
  it -= it == size(endss);
  int np = endss[it][1];
  endss.erase(begin(endss) + it);
  blocks[np].push_back({y, ind, B, B, B});
  if (size(blocks[p]) && p != np)
    endss.erase(find(all(endss), ari2{blocks[p].back()[0], p}));
 
  if (p < np) {
    upd(np, true);
    upd(p, false);
  } else if (p > np) {
    upd(p, false);
    upd(np, true);
  } else {
    upd(p, true);
  }
  p = np; // lol
 
  if (++it_cnt % B == 0)
    recalc();
 
  int cb = endss[0][1], ce = 0, ret = 0;
  while (cb < B) {
    if (blocks[cb][ce][2] != cb) {
      int it_r = lower_bound(all(endss), ari2{blocks[cb][ce][0]+L+1, 0}) - begin(endss);
      int r = it_r < size(endss) ? endss[it_r][1] : B;
      int rr = r == B ? 0 : lower_bound(all(blocks[r]), array<int, 5>{blocks[cb][ce][0]+L+1, 0, 0, 0, 0}) - begin(blocks[r]);
      blocks[cb][ce] = {blocks[cb][ce][0], blocks[cb][ce][1], r, rr, 1};
    }
    ret += blocks[cb][ce][4];
    int nb = blocks[cb][ce][2], ne = blocks[cb][ce][3];
    cb = nb, ce = ne;
  }
 
  return ret;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8536 KB Output is correct
2 Correct 2 ms 8544 KB Output is correct
3 Correct 1 ms 8548 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8536 KB Output is correct
2 Correct 2 ms 8544 KB Output is correct
3 Correct 1 ms 8548 KB Output is correct
4 Correct 2 ms 8536 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8536 KB Output is correct
2 Correct 2 ms 8544 KB Output is correct
3 Correct 1 ms 8548 KB Output is correct
4 Correct 2 ms 8536 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct
7 Correct 249 ms 10384 KB Output is correct
8 Correct 338 ms 10824 KB Output is correct
9 Correct 432 ms 12492 KB Output is correct
10 Correct 479 ms 12236 KB Output is correct
11 Correct 436 ms 12228 KB Output is correct
12 Correct 759 ms 13004 KB Output is correct
13 Correct 911 ms 12236 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8536 KB Output is correct
2 Correct 2 ms 8544 KB Output is correct
3 Correct 1 ms 8548 KB Output is correct
4 Correct 2 ms 8536 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct
7 Correct 249 ms 10384 KB Output is correct
8 Correct 338 ms 10824 KB Output is correct
9 Correct 432 ms 12492 KB Output is correct
10 Correct 479 ms 12236 KB Output is correct
11 Correct 436 ms 12228 KB Output is correct
12 Correct 759 ms 13004 KB Output is correct
13 Correct 911 ms 12236 KB Output is correct
14 Correct 306 ms 11336 KB Output is correct
15 Correct 393 ms 11088 KB Output is correct
16 Correct 1140 ms 12968 KB Output is correct
17 Correct 1402 ms 15036 KB Output is correct
18 Correct 1331 ms 13976 KB Output is correct
19 Correct 1578 ms 14156 KB Output is correct
20 Correct 1375 ms 14784 KB Output is correct
21 Correct 1248 ms 15000 KB Output is correct
22 Correct 1712 ms 13508 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8536 KB Output is correct
2 Correct 2 ms 8544 KB Output is correct
3 Correct 1 ms 8548 KB Output is correct
4 Correct 2 ms 8536 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct
7 Correct 249 ms 10384 KB Output is correct
8 Correct 338 ms 10824 KB Output is correct
9 Correct 432 ms 12492 KB Output is correct
10 Correct 479 ms 12236 KB Output is correct
11 Correct 436 ms 12228 KB Output is correct
12 Correct 759 ms 13004 KB Output is correct
13 Correct 911 ms 12236 KB Output is correct
14 Correct 306 ms 11336 KB Output is correct
15 Correct 393 ms 11088 KB Output is correct
16 Correct 1140 ms 12968 KB Output is correct
17 Correct 1402 ms 15036 KB Output is correct
18 Correct 1331 ms 13976 KB Output is correct
19 Correct 1578 ms 14156 KB Output is correct
20 Correct 1375 ms 14784 KB Output is correct
21 Correct 1248 ms 15000 KB Output is correct
22 Correct 1712 ms 13508 KB Output is correct
23 Correct 4821 ms 24404 KB Output is correct
24 Correct 4793 ms 23340 KB Output is correct
25 Correct 4358 ms 22848 KB Output is correct
26 Correct 4986 ms 24344 KB Output is correct
27 Correct 5518 ms 23092 KB Output is correct
28 Correct 955 ms 13872 KB Output is correct
29 Correct 897 ms 14128 KB Output is correct
30 Correct 946 ms 13872 KB Output is correct
31 Correct 892 ms 13888 KB Output is correct
32 Correct 3869 ms 22244 KB Output is correct
33 Correct 2717 ms 23200 KB Output is correct
34 Correct 4425 ms 22972 KB Output is correct
35 Correct 2798 ms 27228 KB Output is correct
36 Correct 1345 ms 23092 KB Output is correct
37 Correct 5327 ms 26732 KB Output is correct
38 Correct 8593 ms 21436 KB Output is correct
39 Correct 7375 ms 23772 KB Output is correct
40 Correct 8982 ms 22552 KB Output is correct
41 Correct 5932 ms 24056 KB Output is correct
42 Correct 5947 ms 22504 KB Output is correct