oj.uz

답안 #445361

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
445361 2021-07-17T16:09:32 Z prvocislo 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
0 / 100
 2 ms 1612 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[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.empty() && 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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1612 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1612 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1612 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1612 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1612 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -