| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 764430 | boris_mihov | 코끼리 (Dancing Elephants) (IOI11_elephants) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "elephants.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <vector>
#include <set>
typedef long long llong;
const int MAXNUM = 1000000000;
const int BUCKET_SIZE = 1005;
const int MAXN = 150000 + 10;
const int INF = 2e9;
int n, len;
int a[MAXN];
std::vector <int> nums[BUCKET_SIZE];
std::vector <std::pair <int,int>> dp[BUCKET_SIZE];
void fix(int idx)
{
dp[idx].resize(nums[idx].size());
int ptr = nums[idx].size();
for (int i = (int)nums[idx].size() - 1 ; i >= 0 ; --i)
{
while (ptr > 0 && nums[idx][i] + len < nums[idx][ptr - 1])
{
ptr--;
}
if (ptr == nums[idx].size())
{
dp[idx][i] = {1, nums[idx][i] + len};
} else
{
dp[idx][i] = dp[idx][ptr];
dp[idx][i].first++;
}
}
}
void erase(int idx, int val)
{
for (int i = 0 ; i < nums[idx].size() ; ++i)
{
if (nums[idx][i] == val)
{
nums[idx].erase(nums[idx].begin() + i);
break;
}
}
fix(idx);
}
void insert(int idx, int val)
{
bool inserted = false;
for (int i = 0 ; i < nums[idx].size() ; ++i)
{
if (val < nums[idx][i])
{
nums[idx].insert(nums[idx].begin() + i, val);
inserted = true;
break;
}
}
if (!inserted)
{
nums[idx].push_back(val);
}
fix(idx);
}
std::multiset <int> ms;
void init(int N, int L, int X[])
{
n = N;
len = L;
for (int i = 1 ; i <= n ; ++i)
{
a[i] = X[i - 1];
if (!ms.count(a[i]))
{
nums[a[i] / BUCKET_SIZE].push_back(a[i]);
}
ms.insert(a[i]);
}
for (int i = 0 ; i < BUCKET_SIZE ; ++i)
{
std::sort(nums[i].begin(), nums[i].end());
fix(i);
}
}
int update(int idx, int y)
{
idx++;
ms.erase(ms.find(a[idx]));
if (!ms.count(a[idx]))
{
erase(a[idx] / BUCKET_SIZE, a[idx]);
}
a[idx] = y;
if (!ms.count(y))
{
insert(y / BUCKET_SIZE, y);
}
ms.insert(y);
int res = 0;
int coveredTo = -1;
for (int bucket = 0 ; bucket < BUCKET_SIZE ; ++bucket)
{
if (nums[bucket].empty())
{
continue;
}
std::sort(nums[bucket].begin(), nums[bucket].back());
if (coveredTo >= nums[bucket].back())
{
continue;
}
int l = -1, r = nums[bucket].size() - 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (nums[bucket][mid] <= coveredTo) l = mid;
else r = mid;
}
res += dp[bucket][r].first;
coveredTo = dp[bucket][r].second;
}
return res;
}