oj.uz

Submission #856431

# Submission time Handle Problem Language Result Execution time Memory
856431 2023-10-03T13:19:22 Z NeroZein Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 22900 KB 
#include "elephants.h"
#include "bits/stdc++.h"
 
using namespace std; 

const int B = 400; 

int n, l;
int tot, qc; 
vector<int> a; 
vector<int> bucket;
vector<int> nxt, cnt;
vector<int> in_bucket[B]; 

void calc(int bucket_num) {
  int m = in_bucket[bucket_num].size();
  if (m == 0) {
    return;
  }
  int p = m - 1;
  for (int i = m - 1; i >= 0; --i) {
    int cur = in_bucket[bucket_num][i]; 
    while (a[in_bucket[bucket_num][p]] - a[cur] > l) {
      p--;
    }
    if (p == m - 1) {
      cnt[cur] = 1;
      nxt[cur] = a[cur] + l; 
    } else {
      nxt[cur] = nxt[in_bucket[bucket_num][p + 1]]; 
      cnt[cur] = cnt[in_bucket[bucket_num][p + 1]] + 1; 
    }
  }
}

void init(int N_, int L, int X[]) {
  n = N_, l = L;
  a.resize(n);  
  cnt.resize(n);
  nxt.resize(n); 
  bucket.resize(n); 
  tot = (n - 1) / B; 
  for (int i = 0; i < n; ++i) {
    a[i] = X[i];
  }
  for (int i = 0; i < n; ++i) {
    in_bucket[i / B].push_back(i); 
    bucket[i] = i / B;
  }
  for (int i = 0; i <= tot; ++i) {
    calc(i); 
  }
}

int search(int x) {
  for (int i = 0; i <= tot; ++i) {
    if (!in_bucket[i].empty() && a[in_bucket[i].back()] > x) {
      for (int j : in_bucket[i]) {
        if (a[j] > x) {
          return j; 
        }
      }
      assert(false); 
    }
  }
  return -1; 
}

int query() {
  int ret = 0;
  int x = -1;
  while (true) {
    int nb = search(x);
    if (nb == -1) {
      break;
    }
    x = nxt[nb];
    ret += cnt[nb];
  }
  return ret;
}

void rebuild() {
  qc = 0; 
  vector<int> p; 
  for (int i = 0; i <= tot; ++i) {
    for (int j : in_bucket[i]) {
      p.push_back(j); 
    }
    in_bucket[i].clear(); 
  }
  for (int i = 0; i < n; ++i) {
    in_bucket[i / B].push_back(p[i]); 
    bucket[p[i]] = i / B; 
  }
  for (int i = 0; i <= tot; ++i) {
    calc(i); 
  }
}
 
int update(int i, int y) {
  qc++;
  if (qc == B) {
    rebuild(); 
  }
  int b1 = bucket[i];
  in_bucket[b1].erase(find(in_bucket[b1].begin(), in_bucket[b1].end(), i));
  int b2 = search(y);
  if (b2 == -1) {
    b2 = tot; 
  } else {
    b2 = bucket[b2];
  }
  bucket[i] = b2; 
  bool f = false; 
  for (int j = 0; j < (int) in_bucket[b2].size(); ++j) {
    if (a[in_bucket[b2][j]] > y) {
      f = true; 
      in_bucket[b2].insert(in_bucket[b2].begin() + j, i);
      break; 
    }
  }
  if (!f) {
    in_bucket[b2].push_back(i); 
  }
  a[i] = y; 
  calc(b1);
  calc(b2); 
  return query(); 
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6580 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 177 ms 9236 KB Output is correct
8 Correct 209 ms 9696 KB Output is correct
9 Correct 591 ms 10304 KB Output is correct
10 Correct 844 ms 10436 KB Output is correct
11 Correct 754 ms 10492 KB Output is correct
12 Correct 944 ms 10556 KB Output is correct
13 Correct 943 ms 11688 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6580 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 177 ms 9236 KB Output is correct
8 Correct 209 ms 9696 KB Output is correct
9 Correct 591 ms 10304 KB Output is correct
10 Correct 844 ms 10436 KB Output is correct
11 Correct 754 ms 10492 KB Output is correct
12 Correct 944 ms 10556 KB Output is correct
13 Correct 943 ms 11688 KB Output is correct
14 Correct 295 ms 10992 KB Output is correct
15 Correct 395 ms 10960 KB Output is correct
16 Correct 1401 ms 12464 KB Output is correct
17 Correct 2020 ms 13140 KB Output is correct
18 Correct 2121 ms 13196 KB Output is correct
19 Correct 1765 ms 13312 KB Output is correct
20 Correct 2049 ms 13364 KB Output is correct
21 Correct 2021 ms 13444 KB Output is correct
22 Correct 2141 ms 12988 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6580 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 177 ms 9236 KB Output is correct
8 Correct 209 ms 9696 KB Output is correct
9 Correct 591 ms 10304 KB Output is correct
10 Correct 844 ms 10436 KB Output is correct
11 Correct 754 ms 10492 KB Output is correct
12 Correct 944 ms 10556 KB Output is correct
13 Correct 943 ms 11688 KB Output is correct
14 Correct 295 ms 10992 KB Output is correct
15 Correct 395 ms 10960 KB Output is correct
16 Correct 1401 ms 12464 KB Output is correct
17 Correct 2020 ms 13140 KB Output is correct
18 Correct 2121 ms 13196 KB Output is correct
19 Correct 1765 ms 13312 KB Output is correct
20 Correct 2049 ms 13364 KB Output is correct
21 Correct 2021 ms 13444 KB Output is correct
22 Correct 2141 ms 12988 KB Output is correct
23 Execution timed out 9091 ms 22900 KB Time limit exceeded
24 Halted 0 ms 0 KB -