| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 317497 | vitkishloh228 | Dancing Elephants (IOI11_elephants) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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[150000 + 5];
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] + k) 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 ind = lower_bound(block[ptr].begin(), block[ptr].end(), x) - block[ptr].begin();
if (b) {
block[ptr].insert(block[ptr].begin() + ind, x);
}
else {
block[ptr].erase(block[ptr].begin() + ind);
}
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;
}