Submission #671787

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
671787	2022-12-14T01:25:45 Z	Hacv16	Dancing Elephants (IOI11_elephants)	C++17	Compilation error	0 ms	0 KB

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 MAX = 1e3 + 15;

int n, L, x[MAX], block[MAX], T, dist[MAX], dp[MAX], query;
vector<int> ord, blocks[MAX];

bool cmp(int i, int j){ return x[i] < x[j]; }

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];

  for(int i = 0; i < n; i++) 
      ord.push_back(i);
}
 
void buildBlock(int b){
  int s = sz(blocks[b]), lst = x[blocks[b].back()];

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

    if(lst - curPos <= l){
      dp[curId] = 1;
      dist[curId] = curPos + L;

    }else{
      while(x[blocks[b][r]] - curPos > l) r--;

      dp[curId] = dp[blocks[b][r]] + 1;
      dist[curId] = dist[blocks[b][r]];
    }
  }
}

void build(){
  for(int i = 0; i <= (n - 1) / T; i++) 
      blocks[i].clear();

  sort(all(ord), cmp);

  for(int i = 0; i < n; i++){
    block[ord[i]] = i / T;
    blocks[i / T].push_back(ord[i]);
  }

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

int query(){
  int resp = 0;

  for(int i = 0; i <= (n - 1) / T, t = -1; i++){
    if(blocks[i].empty() || t >= x[blocks[i].back()]) continue;

    int l = 0, r = sz(blocks[i]) - 1, jump = 0;

    while(l <= r){
      int m = (l + r) >> 1;
      int curPos = x[blocks[i]][m];

      if(curPos > t) jump = m, l = m + 1;
      else r = m - 1;
    }

    resp += dp[blocks[i][jump]];
    t = dist[blocks[i][jump]]; 
  }

  return resp;
}

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

  //Remove from current block
  vector<int> aux;

  for(auto x : block[i]){
    if(x == i) continue;
    aux.push_back(x);
  }

  swap(aux, blocks[block[i]]);
  buildBlock(block[i]);

  //Add to new block
  aux.clear();

  int newBlock = 0;

  for(int j = 0; j <= (n - 1) / T; j++)
    if(blocks[j].size() && blocks[j].back() >= y){ newBlock = j; break; }

  aux.push_back(i);
  x[i] = y;

  vector<int> ret(sz(blocks[newBlock]) + 1);
  merge(aux.begin(), aux.end(), blocks[newBlock].begin(), blocks[newBlock].end(), ret.begin(), cmp);

  swap(ret, blocks[newBlock]);
  buildBlock(newBlock);

  return query();
}

Compilation message

elephants.cpp:61:11: error: 'int query()' redeclared as different kind of entity
   61 | int query(){
      |           ^
elephants.cpp:11:54: note: previous declaration 'int query'
   11 | int n, L, x[MAX], block[MAX], T, dist[MAX], dp[MAX], query;
      |                                                      ^~~~~
elephants.cpp: In function 'int query()':
elephants.cpp:64:36: error: 't' was not declared in this scope
   64 |   for(int i = 0; i <= (n - 1) / T, t = -1; i++){
      |                                    ^
elephants.cpp:71:21: error: no match for 'operator[]' (operand types are 'int [1015]' and 'std::vector<int>')
   71 |       int curPos = x[blocks[i]][m];
      |                     ^
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:91:23: error: 'begin' was not declared in this scope
   91 |   for(auto x : block[i]){
      |                       ^
elephants.cpp:91:23: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from elephants.cpp:2:
/usr/include/c++/10/valarray:1224:5: note:   'std::begin'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from elephants.cpp:2:
/usr/include/c++/10/bits/fs_dir.h:549:3: note:   'std::filesystem::__cxx11::begin'
  549 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
elephants.cpp:91:23: error: 'end' was not declared in this scope
   91 |   for(auto x : block[i]){
      |                       ^
elephants.cpp:91:23: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from elephants.cpp:2:
/usr/include/c++/10/valarray:1244:5: note:   'std::end'
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from elephants.cpp:2:
/usr/include/c++/10/bits/fs_dir.h:554:3: note:   'std::filesystem::__cxx11::end'
  554 |   end(recursive_directory_iterator) noexcept
      |   ^~~
elephants.cpp:116:16: error: 'query' cannot be used as a function
  116 |   return query();
      |                ^