oj.uz

Submission #445362

# Submission time Handle Problem Language Result Execution time Memory
445362 2021-07-17T16:11:31 Z prvocislo Dancing Elephants (IOI11_elephants) C++17
100 / 100
 4702 ms 13800 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1.5e5 + 5, siz = 605, nsiz = maxn / siz + 5;
//const int maxn = 10, siz = 5, nsiz = maxn / siz + 1;
int n, l, q = 0;
struct block
{
  vector<int> x, cnt, len;
  void rebuild() // predpokladam ze pole x je stale striedene
  {
    int n = x.size(); cnt.resize(n), len.resize(n);
    for (int i = n - 1, j = n; i >= 0; i--) // j je prvy slonik na ktoreho nedociahneme
    {
      while (j > 0 && x[j-1] > x[i] + l) j--;
      cnt[i] = (j == n ? 0 : cnt[j]) + 1;
      len[i] = (j == n ? x[i] + l : len[j]);
    }
  }
} b[nsiz];
vector<int> pos(maxn); // pozicia slonika s tymto indexom
void rebuild()
{
  vector<int> x;
  for (int i = 0; i < nsiz; i++) 
  {
    for (const int &j : b[i].x) x.push_back(j);
    b[i].x.clear();
  }
  for (int i = 0; i < n; i++) b[i/siz].x.push_back(x[i]);
  for (int i = 0; i < nsiz; i++) b[i].rebuild();
}
void init(int N, int L, int X[])
{
  n = N, l = L;
  for (int i = 0; i < n; i++) pos[i] = X[i], b[0].x.push_back(X[i]);
}
void rmv(int val)
{
  for (int i = 0; i < nsiz; i++) if (b[i].x.size() && b[i].x[0] <= val && val <= b[i].x.back())
  {
    int it = lower_bound(b[i].x.begin(), b[i].x.end(), val) - b[i].x.begin();
    b[i].x.erase(b[i].x.begin() + it);
    b[i].rebuild();
    break;
  }
}
void add(int val)
{
  for (int i = 0, p = -1; i < nsiz; i++)
  {
    if (i == nsiz-1 || (b[i].x.size() && p <= val && val <= b[i].x.back()))
    {
      int it = lower_bound(b[i].x.begin(), b[i].x.end(), val) - b[i].x.begin();
      b[i].x.insert(b[i].x.begin() + it, val);
      b[i].rebuild();
      break;
    }
    if (!b[i].x.empty()) p = b[i].x.back();
  }
}
int update(int i, int y)
{
  if ((q++)%nsiz == 0) rebuild();
  rmv(pos[i]);
  pos[i] = y;
  add(pos[i]);
  int cover = -1, ans = 0;
  for (int i = 0; i < nsiz; i++)
  {
    if (b[i].x.empty()) continue;
    int f = upper_bound(b[i].x.begin(), b[i].x.end(), cover) - b[i].x.begin();
    if (f == b[i].x.size()) continue;
    ans += b[i].cnt[f];
    cover = b[i].len[f];
  }
  return ans;
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:74:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     if (f == b[i].x.size()) continue;
      |         ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 648 ms 1988 KB Output is correct
8 Correct 670 ms 3252 KB Output is correct
9 Correct 493 ms 4804 KB Output is correct
10 Correct 409 ms 4536 KB Output is correct
11 Correct 436 ms 4432 KB Output is correct
12 Correct 852 ms 5068 KB Output is correct
13 Correct 403 ms 4208 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 648 ms 1988 KB Output is correct
8 Correct 670 ms 3252 KB Output is correct
9 Correct 493 ms 4804 KB Output is correct
10 Correct 409 ms 4536 KB Output is correct
11 Correct 436 ms 4432 KB Output is correct
12 Correct 852 ms 5068 KB Output is correct
13 Correct 403 ms 4208 KB Output is correct
14 Correct 567 ms 3940 KB Output is correct
15 Correct 1004 ms 4196 KB Output is correct
16 Correct 1460 ms 5616 KB Output is correct
17 Correct 1463 ms 6808 KB Output is correct
18 Correct 1651 ms 6720 KB Output is correct
19 Correct 776 ms 6304 KB Output is correct
20 Correct 1473 ms 6756 KB Output is correct
21 Correct 1408 ms 6748 KB Output is correct
22 Correct 682 ms 5768 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 648 ms 1988 KB Output is correct
8 Correct 670 ms 3252 KB Output is correct
9 Correct 493 ms 4804 KB Output is correct
10 Correct 409 ms 4536 KB Output is correct
11 Correct 436 ms 4432 KB Output is correct
12 Correct 852 ms 5068 KB Output is correct
13 Correct 403 ms 4208 KB Output is correct
14 Correct 567 ms 3940 KB Output is correct
15 Correct 1004 ms 4196 KB Output is correct
16 Correct 1460 ms 5616 KB Output is correct
17 Correct 1463 ms 6808 KB Output is correct
18 Correct 1651 ms 6720 KB Output is correct
19 Correct 776 ms 6304 KB Output is correct
20 Correct 1473 ms 6756 KB Output is correct
21 Correct 1408 ms 6748 KB Output is correct
22 Correct 682 ms 5768 KB Output is correct
23 Correct 3636 ms 13424 KB Output is correct
24 Correct 3963 ms 13600 KB Output is correct
25 Correct 2839 ms 13220 KB Output is correct
26 Correct 3072 ms 13156 KB Output is correct
27 Correct 3962 ms 12732 KB Output is correct
28 Correct 2408 ms 5736 KB Output is correct
29 Correct 2375 ms 5700 KB Output is correct
30 Correct 2411 ms 5824 KB Output is correct
31 Correct 2323 ms 5696 KB Output is correct
32 Correct 2741 ms 12340 KB Output is correct
33 Correct 2431 ms 11612 KB Output is correct
34 Correct 2406 ms 12400 KB Output is correct
35 Correct 2804 ms 13800 KB Output is correct
36 Correct 2735 ms 12156 KB Output is correct
37 Correct 3405 ms 13696 KB Output is correct
38 Correct 2521 ms 11360 KB Output is correct
39 Correct 2739 ms 12728 KB Output is correct
40 Correct 2594 ms 11648 KB Output is correct
41 Correct 4699 ms 13444 KB Output is correct
42 Correct 4702 ms 13528 KB Output is correct