| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 358997 | hivakarami | 코끼리 (Dancing Elephants) (IOI11_elephants) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "elephants.h"
#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 = 15e4 + 100;
const int sq = 500;
const ll mod = 1e9 + 7;
const ll inf = 1e16;
int n, len, q = 0, m = 0;
int a[N], id[N];
vector<int> v[sq], tmp;
int nx[sq][N], dp[sq][N];
//*
void init(int N, int L, int X[])
{
n = N;
len = L;
a = X;
}
//*/
void bld(int x)
{
int sz = v[x].size();
int pt = sz;
for(int i = sz - 1; i >= 0; i--)
{
while(pt > 0 && v[x][pt-1] > v[x][i] + len)
pt--;
if(pt >= sz)
{
dp[x][i] = 1;
nx[x][i] = v[x][i] + len + 1;
}
else
{
dp[x][i] = dp[x][pt] + 1;
nx[x][i] = nx[x][pt];
}
}
}
void build()
{
vector<pair<int, int>> vec;
for(int i = 0; i < m; i++)
v[i].clear();
for(int i = 0; i < n; i++)
vec.push_back({a[i], i});
sort(vec.begin(), vec.end());
m = 0;
for(int i = 0; i < n; i++)
{
if(v[m].size() == sq)
bld(m++);
v[m].push_back(vec[i].f);
id[vec[i].s] = m;
}
bld(m++);
}
void del(int i)
{
tmp.clear();
int j = id[i];
bool fl = true;
for(auto x : v[j])
{
if(fl && x == a[i])
fl = false;
else
tmp.push_back(x);
}
v[j] = tmp;
bld(j);
}
void add(int i, int y)
{
//cout << "add" << ' ' << i << ' ' << y << endl;
tmp.clear();
int j = 0;
while(j+1 < m && v[j+1][0] > y)
j++;
bool fl = false;
for(auto x : v[j])
{
if(!fl && x > y)
{
tmp.push_back(y);
fl = true;
}
tmp.push_back(x);
}
if(!fl)
tmp.push_back(y);
v[j] = tmp;
a[i] = y;
id[i] = j;
bld(j);
}
int get_ans()
{
int res = 0, pt = 0, c = v[0][0];
while(pt < m)
{
while(pt < m && v[pt].back() < c)
pt++;
if(pt >= m)
break;
int k = lower_bound(v[pt].begin(), v[pt].end(), c) - v[pt].begin();
res += dp[pt][k];
c = nx[pt][k];
}
return res;
}
int update(int i, int y)
{
if(q%(sq-2) == 0)
build();
q++;
del(i);
add(i, y);
return get_ans();
}
/*
int main()
{
cin >> n >> len;
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
int qu;
cin >> qu;
while(qu--)
{
int a, b;
cin >> a >> b;
//cout << "///////////" << endl;
cout << update(a, b) << '\n';
/*
for(int i = 0; i < m; i++)
{
for(auto x : v[i])
cout << x << ' ';
cout << endl;
}
//*/
}
return 0;
}
//*/