| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 352344 | hivakarami | 코끼리 (Dancing Elephants) (IOI11_elephants) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define f first
#define s second
const int N = 1e5 + 5;
const int sq = 500;
const ll mod = 1e9 + 7;
const ll inf = 1e16;
int n, len, q = 0;
vector<int> v[sq], tmp;
int nx[sq][N], dp[sq][N], x[N];
map<int, int> cnt;
/*
void init(int N, int L, int X[])
{
n = N;
len = L;
x = X;
for(int i = 0; i < n; i++)
cnt[x[i]]++;
}
//*/
void bld(int id)
{
//cout << "id : "<< id << endl;
int m = v[id].size();
nx[id][m-1] = v[id][m-1] + len;
dp[id][m-1] = 1;
for(int i = m - 2; i >= 0; i--)
{
if(v[id][m-1] > v[id][i]+len)
{
auto it = upper_bound(v[id].begin(), v[id].end(), v[id][i]+len);
int p = it - v[id].begin();
nx[id][i] = nx[id][p];
dp[id][i] = dp[id][p] + 1;
}
else
{
dp[id][i] = 1;
nx[id][i] = v[id][i] + len;
}
}
//for(int i = m-1; i >= 0; i--)
//cout << nx[id][i] << ' ' << dp[id][i] << endl;
}
void build()
{
sort(x, x + n);
n = unique(x, x+n) - x;
for(int i = 0; i < sq; i++)
v[i].clear();
int id = 0;
for(int i = 0; i < n; i++)
{
v[id].push_back(x[i]);
if(v[id].size() == sq)
{
bld(id);
id++;
}
}
if(v[id].size() != 0)
bld(id);
//cout << "////////" << endl;
}
void add(int k, bool b)
{
int id = 0;
for(int i = 0; i < sq; i++)
{
if(v[i].size() != 0 && v[i][0] <= k)
{
id = i;
break;
}
}
//for(auto a : v[id])
//cout << a << ' ';
//cout << endl;
if(!b)
{
tmp = v[id];
v[id].clear();
for(auto y : tmp)
{
if(y != k)
v[id].push_back(y);
}
}
else
{
bool fl = false;
tmp = v[id];
v[id].clear();
for(auto y : tmp)
{
if(y > k)
{
v[id].push_back(k);
v[id].push_back(y);
fl = true;
}
}
if(!fl)
v[id].push_back(k);
}
bld(id);
}
int update(int i, int y)
{
if(q%sq == 0)
build();
q++;
cnt[x[i]]--;
if(cnt[x[i]] == 0)
add(x[i], 0);
x[i] = y;
if(cnt[x[i]] == 0)
add(x[i], 1);
cnt[y]++;
int j = 0, ans = 0;
for(int i = 0; i < sq; i++)
{
if(j < v[i].size())
ans += dp[i][j];
if(v[i+1].empty())
break;
j = upper_bound(v[i+1].begin(), v[i+1].end(), nx[i][j]) - v[i+1].begin();
}
return ans;
}
/*
int main()
{
cin >> n >> len;
for(int i = 0; i < n; i++)
{
cin >> x[i];
cnt[x[i]]++;
}
int a, b;
cin >> a >> b;
cout << update(a, b) << endl;
return 0;
}
*/