Submission #671962

#	Time	Username	Problem	Language	Result	Execution time	Memory
671962		Hacv16	Dancing Elephants (IOI11_elephants)	C++17	Compilation error	0 ms	0 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>
 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;
const int MAXN = 1e6 + 16;
const int MAX = 3e3 + 15;

int n, L, x[MAXN], block[MAXN], T, dp[MAX][MAX], d[MAX][MAX];
vector<int> blocks[MAX];

void init(int n_, int l_, int x_[]){
  n = n_, L = l_;
  T = sqrt(n) + 1;
 
  for(int i = 0; i < n; i++)
    x[i] = x_[i], blocks[i / T].push_back(x[i]);
}

void buildBlock(int b){
  if(blocks[b].empty()) return;
  int s = sz(blocks[b]);

  for(int l = s - 1, r = s; l >= 0; l--){
    int curX = blocks[b][l];

    while(blocks[b][r - 1] - curX > L) r--;

    if(r == s){
      dp[b][l] = 1;
      d[b][l] = curX + L;

    }else{
      dp[b][l] = dp[b][r] + 1;
      d[b][l] = d[b][r];
    }
  }
}

void build(){
  vector<int> aux;

  for(int i = 0; i <= (n - 1) / T; i++){
    for(auto& x : blocks[i]) aux.push_back(x);
    blocks[i].clear();
  }

  for(int i = 0; i < n; i++)
    blocks[i / T].push_back(aux[i]);

  for(int i = 0; i <= (n - 1) / T; i++) 
    buildBlock(i);
}

int getBlock(int x){
  for(int i = (n - 1) / T; i >= 0; i--)
    if(blocks[i].size() && blocks[i][0] <= x) return i;
  return 0;
}

int query(void){
  int ans = 0;

  for(int i = 0, r = -1; i <= (n - 1) / T; i++){
    int idx = upper_bound(all(blocks[i]), r) - blocks[i].begin();
    if(idx >= blocks[i].size()) continue;

    ans += dp[i][idx];
    r = d[i][idx];
  }

  return ans;
}

int update(int i, int y){ 
  if(q++ % T == 0) build();

  int b = getBlock(x[i]);
  auto it = lower_bound(all(blocks[b]), x[i]);
  blocks[b].erase(it);

  buildBlock(b);

  x[i] = y;
  int nb = getBlock(y);
  it = lower_bound(all(blocks[nb]), x[i]);

  if(it == blocks[nb].end()) blocks[nb].push_back(x[i]);
  else blocks[nb].insert(it, x[i]);

  buildBlock(nb);

  return query();
}

Compilation message (stderr)

elephants.cpp: In function 'int query()':
elephants.cpp:69:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     if(idx >= blocks[i].size()) continue;
      |        ~~~~^~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:79:6: error: 'q' was not declared in this scope
   79 |   if(q++ % T == 0) build();
      |      ^