제출 #445357

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

elephants

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

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

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