oj.uz

Submission #445357

# Submission time Handle Problem Language Result Execution time Memory
445357 2021-07-17T15:30:36 Z prvocislo Dancing Elephants (IOI11_elephants) C++17
26 / 100
 19 ms 2892 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1.5e5, siz = 600, nsiz = maxn / siz + 1;
//const int maxn = 10, siz = 5, nsiz = maxn / siz + 1;
int n, l, q = 0;
struct block
{
  vector<pair<int, int> > x; // {hodnota, pozicia}
  vector<int> 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].first > x[i].first + l) j--;
      cnt[i] = (j == n ? 0 : cnt[j]) + 1;
      len[i] = (j == n ? x[i].first + l : len[j]);
    }
  }
} b[nsiz];
vector<int> pos(maxn); // pozicia slonika s tymto indexom
void rebuild()
{
  vector<pair<int, int> > x;
  for (int i = 0; i < nsiz; i++) 
  {
    for (const pair<int, 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({pos[i], i});
}
void change(int id, bool rmv)
{
  for (int i = 0, p = -1; i < nsiz; i++) 
  {
    if ((b[i].x.size() && p < pos[id] && pos[id] <= b[i].x.back().first) || (!rmv && i == nsiz-1))
    {
      int j = lower_bound(b[i].x.begin(), b[i].x.end(), make_pair(pos[id], id)) - b[i].x.begin();
      if (rmv) 
        b[i].x.erase(b[i].x.begin() + j);
      else b[i].x.insert(b[i].x.begin() + j, make_pair(pos[id], id));
      b[i].rebuild();
      break;
    }
    if (b[i].x.size()) p = b[i].x.back().first;
  }
}
int update(int i, int y)
{
  if ((q++)%nsiz == 0) rebuild();
  change(i, true);
  pos[i] = y;
  change(i, false);
  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(), make_pair(cover, -1)) - 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:67:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     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 916 KB Output is correct
6 Correct 1 ms 912 KB Output is correct

Subtask #3
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 916 KB Output is correct
6 Correct 1 ms 912 KB Output is correct
7 Incorrect 19 ms 2892 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
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 916 KB Output is correct
6 Correct 1 ms 912 KB Output is correct
7 Incorrect 19 ms 2892 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
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 916 KB Output is correct
6 Correct 1 ms 912 KB Output is correct
7 Incorrect 19 ms 2892 KB Output isn't correct
8 Halted 0 ms 0 KB -