oj.uz

Submission #856429

# Submission time Handle Problem Language Result Execution time Memory
856429 2023-10-03T13:16:07 Z NeroZein Dancing Elephants (IOI11_elephants) C++17
26 / 100
 213 ms 23860 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 * 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; 
        }
      }
    }
  }
  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];
  }
  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 2 ms 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10840 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 181 ms 11100 KB Output is correct
8 Correct 213 ms 11796 KB Output is correct
9 Runtime error 31 ms 23860 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10840 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 181 ms 11100 KB Output is correct
8 Correct 213 ms 11796 KB Output is correct
9 Runtime error 31 ms 23860 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10840 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 181 ms 11100 KB Output is correct
8 Correct 213 ms 11796 KB Output is correct
9 Runtime error 31 ms 23860 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -