Submission #317501

#	Time	Username	Problem	Language	Result	Execution time	Memory
317501		vitkishloh228	Dancing Elephants (IOI11_elephants)	C++14	Compilation error	0 ms	0 KiB

elephants

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;
unordered_map<int, int> mp;
int n, L, bcnt;
const int k = 400;
vector<pair<int, int>> dp[k + 5];
vector<int> block[k];
int pos[150005];
int R[k + 5];
void init(int _n, int _L, vector<int> x) {
    n = _n, L = _L;
    for (int i = 0; i < n; ++i) {
        ++mp[pos[i] = x[i]];
    }
}
void solve_block(int id) {
    vector<int>& v = block[id];
    dp[id].clear();
    dp[id].resize(v.size());
    for (int i = v.size() - 1, j = v.size(); ~i; i--) {
        while (v[j - 1] > v[i] + L) j--;
        if (j < v.size()) {
            dp[id][i] = dp[id][j];
            dp[id][i].second++;
        } else {
            dp[id][i] = make_pair(v[i] + L, 1);
        }
    }
}
void rebuild() {
    bcnt = 0;
    for (auto p : mp) {
        if (!bcnt || block[bcnt - 1].size() >= k)
            block[bcnt++].clear();
        block[bcnt - 1].push_back(p.first);
    }
    for (int i = 0; i < bcnt; ++i) {
        if (i + 1 < bcnt) {
            R[i] = block[i + 1][0] - 1;
        } else {
            R[i] = 1e9;
        }
        solve_block(i);
    }
}
void add(int x, bool b) {
    int ptr = -1;
    while (R[++ptr] < x) {
        int p = -1;
        p = 1;
    }
    int ind = lower_bound(block[ptr].begin(), block[ptr].end(), x) - block[ptr].begin();
    if (b) {
        block[ptr].insert(block[ptr].begin() + ind, x);
    } else if (ind - 1 < block[ptr].size()) {
        block[ptr].erase(block[ptr].begin() + ind - 1);
    }
    solve_block(ptr);
}
int timer = 0;
int update(int i, int y) {
    if (timer++ % k == 0) {
        rebuild();
    }
    if (!--mp[pos[i]]) {
        add(pos[i], 0);
        mp.erase(pos[i]);
    }
    if (!mp[y]) {
        add(y, 1);
    }
    ++mp[y];
    pos[i] = y;
    int ans = 0, cur = -1;
    for (int i = 0; i < bcnt; ++i) {
        int id = upper_bound(block[i].begin(), block[i].end(), cur) - block[i].begin();
        if (id < block[i].size()) {
            ans += dp[i][id].second;
            cur = dp[i][id].first;
        }
    }
    return ans;
}

Compilation message (stderr)

elephants.cpp: In function 'void solve_block(int)':
elephants.cpp:25:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         if (j < v.size()) {
      |             ~~^~~~~~~~~~
elephants.cpp: In function 'void add(int, bool)':
elephants.cpp:52:13: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   52 |         int p = -1;
      |             ^
elephants.cpp:58:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     } else if (ind - 1 < block[ptr].size()) {
      |                ~~~~~~~~^~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:80:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         if (id < block[i].size()) {
      |             ~~~^~~~~~~~~~~~~~~~~
/tmp/ccGvFftd.o: In function `main':
grader.cpp:(.text.startup+0x18): undefined reference to `init(int, int, int*)'
collect2: error: ld returned 1 exit status