Submission #367674

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
367674	2021-02-17T23:33:27 Z	ijxjdjd	Dancing Elephants (IOI11_elephants)	C++14	Compilation error	0 ms	0 KB

elephants

using namespace std;

#include "elephants.h"
#include <bits/stdc++.h>

#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

#define f first
#define s second
#define all(x) begin(x), end(x)
const int MAXN = 150000;
int N;
int BLOCKSIZE;
int L;
const int K = 500;
int REDO = K;
//vector<vector<int>> blocks;
//vector<vector<pair<int, int>>> storeBack;
vector<int> permVec;
int X[MAXN];
int blockId[MAXN];


void recalcBlock(int i, bool needSort) {
    if (blocks[i].size() == 0) {
        return;
    }
    auto comp = [&] (const int& lhs, const int& rhs) {
    return X[lhs] < X[rhs];
    };
    if (needSort) {
        sort(all(blocks[i]), comp);
    }
    storeBack[i].resize(blocks[i].size());
    int l = blocks[i].size()-1;
    int r = blocks[i].size()-1;
    while (l >= 0) {
        while (X[blocks[i][l]] + L < X[blocks[i][r]]) {
            r--;
        }
        if (r == blocks[i].size()-1) {
            storeBack[i][l] = {1, X[blocks[i][l]] + L};
        }
        else {
            storeBack[i][l] = storeBack[i][r+1];
            storeBack[i][l].f++;
        }
        l--;
    }
}
void rebuild() {
    for (auto& vec : blocks) {
        vec.clear();
    }
    auto comp = [&] (const int& lhs, const int& rhs) {
        return X[lhs] < X[rhs];
    };
    sort(all(permVec), comp);
    for (int i = 0; i < N; i++) {
        blocks[i/K].push_back(permVec[i]);
        blockId[permVec[i]] = i/K;
    }
    for (int i = 0; i < BLOCKSIZE; i++) {
        recalcBlock(i, false);
    }
}
int getAns() {
    int next = -1;
    int res = 0;
    for (int i = 0; i < BLOCKSIZE; i++) {
        if (blocks[i].size() > 0 && next < X[blocks[i].back()]) {
            int low = 0;
            int high = blocks[i].size()-1;
            while (low < high) {
                int mid = (low + high)/2;
                if (next < X[blocks[i][mid]]) {
                    high = mid;
                }
                else {
                    low = mid+1;
                }
            }
            res += storeBack[i][high].f;
            next = storeBack[i][high].s;
        }
    }
    return res;
}
void init(int n, int l, int LD[])
{
  N = n;
  L = l;
  for (int i = 0; i < N; i++) {
    permVec.push_back(i);
    X[i] = LD[i];
  }
  BLOCKSIZE = (N-1)/K + 1;
  blocks.resize(BLOCKSIZE, {});
  storeBack.resize(BLOCKSIZE, {});
  rebuild();
}

int update(int i, int y)
{
    if (REDO == 0) {
        rebuild();
        REDO = K;
    }
    X[i] = y;
    blocks[blockId[i]].erase(find(all(blocks[blockId[i]]), i));
    recalcBlock(blockId[i], false);
    for (int j = 0; j < BLOCKSIZE; j++) {
        if ((j == BLOCKSIZE - 1) || (blocks[j].size() > 0 && X[blocks[j].back()] >= y)) {
            blocks[j].push_back(i);
            blockId[i] = j;
            recalcBlock(j, true);
            break;
        }
    }
    REDO--;
    return getAns();
}

Compilation message

elephants.cpp: In function 'void recalcBlock(int, bool)':
elephants.cpp:26:9: error: 'blocks' was not declared in this scope; did you mean 'blockId'?
   26 |     if (blocks[i].size() == 0) {
      |         ^~~~~~
      |         blockId
elephants.cpp:33:18: error: 'blocks' was not declared in this scope; did you mean 'blockId'?
   33 |         sort(all(blocks[i]), comp);
      |                  ^~~~~~
elephants.cpp:11:22: note: in definition of macro 'all'
   11 | #define all(x) begin(x), end(x)
      |                      ^
elephants.cpp:35:5: error: 'storeBack' was not declared in this scope
   35 |     storeBack[i].resize(blocks[i].size());
      |     ^~~~~~~~~
elephants.cpp:35:25: error: 'blocks' was not declared in this scope; did you mean 'blockId'?
   35 |     storeBack[i].resize(blocks[i].size());
      |                         ^~~~~~
      |                         blockId
elephants.cpp: In function 'void rebuild()':
elephants.cpp:53:22: error: 'blocks' was not declared in this scope; did you mean 'blockId'?
   53 |     for (auto& vec : blocks) {
      |                      ^~~~~~
      |                      blockId
elephants.cpp:61:9: error: 'blocks' was not declared in this scope; did you mean 'blockId'?
   61 |         blocks[i/K].push_back(permVec[i]);
      |         ^~~~~~
      |         blockId
elephants.cpp: In function 'int getAns()':
elephants.cpp:72:13: error: 'blocks' was not declared in this scope; did you mean 'blockId'?
   72 |         if (blocks[i].size() > 0 && next < X[blocks[i].back()]) {
      |             ^~~~~~
      |             blockId
elephants.cpp:84:20: error: 'storeBack' was not declared in this scope
   84 |             res += storeBack[i][high].f;
      |                    ^~~~~~~~~
elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:99:3: error: 'blocks' was not declared in this scope; did you mean 'blockId'?
   99 |   blocks.resize(BLOCKSIZE, {});
      |   ^~~~~~
      |   blockId
elephants.cpp:100:3: error: 'storeBack' was not declared in this scope
  100 |   storeBack.resize(BLOCKSIZE, {});
      |   ^~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:111:5: error: 'blocks' was not declared in this scope; did you mean 'blockId'?
  111 |     blocks[blockId[i]].erase(find(all(blocks[blockId[i]]), i));
      |     ^~~~~~
      |     blockId