| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 317501 | vitkishloh228 | Dancing Elephants (IOI11_elephants) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}