제출 #445361

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
445361		prvocislo	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	0 / 100	2 ms	1612 KiB

elephants

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3