| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 559639 | ngpin04 | 코끼리 (Dancing Elephants) (IOI11_elephants) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const int Nmax = 15e4 + 5;
const int Q = 400;
const int K = 1100;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
#include "elephants.h"
#include "grader.cpp"
int ptr[Nmax / K][2 * K + 5];
int dp[Nmax / K][2 * K + 5];
int b[Nmax / K][2 * K + 5];
int v[Nmax / K][2 * K + 5];
pair <int, int> pos[Nmax];
int sz[Nmax];
int x[Nmax];
int n,l,cnt,cntb;
void build(int p, int b[], int ptr[], int dp[], int v[]) {
dp[sz[p]] = 0;
for (int i = sz[p] - 1, j = sz[p]; i >= 0; i--) {
while (v[j - 1] - v[i] > l)
j--;
if (j == sz[p]) {
dp[i] = 0;
ptr[i] = i;
} else {
ptr[i] = ptr[j];
dp[i] = dp[j] + 1;
}
}
}
void del(int i) {
int p = pos[i].fi;
int ind = pos[i].se;
for (int j = ind; j + 1 < sz[p]; j++)
b[p][j] = b[p][j + 1];
sz[p]--;
for (int j = 0; j < sz[p]; j++) {
pos[b[p][j]] = mp(p, j);
v[p][j] = x[b[p][j]];
}
build(p, b[p], ptr[p], dp[p], v[p]);
}
int getmax(int p) {
return v[p][sz[p] - 1];
}
void add(int i) {
int p = 0;
while (p < cntb && (sz[p] > 0 && getmax(p) < x[i]))
p++;
int ind = -1;
while (ind + 1 < sz[p] && v[p][ind + 1] < x[i])
ind++;
for (int j = sz[p]; j - 1 > ind; j--)
b[p][j] = b[p][j - 1];
b[p][ind + 1] = i;
sz[p]++;
for (int j = 0; j < sz[p]; j++) {
pos[b[p][j]] = mp(p, j);
v[p][j] = x[b[p][j]];
}
build(p, b[p], ptr[p], dp[p], v[p]);
}
void rebuild() {
vector <int> ind;
for (int i = 0; i <= cntb; i++) {
for (int j = 0; j < sz[i]; j++)
ind.push_back(b[i][j]);
sz[i] = 0;
}
for (int i = 0; i < n; i++) {
int p = i / l;
int it = ind[i];
pos[it] = mp(p, sz[p]);
b[p][sz[p]++] = it;
}
for (int i = 0; i <= cntb; i++) {
for (int j = 0; j < sz[i]; j++)
v[i][j] = x[b[i][j]];
build(i, b[i], ptr[i], dp[i], v[i]);
}
}
void init(int N, int L, int X[]) {
n = N;
l = L;
for (int i = 0; i < n; i++)
x[i] = X[i];
cntb = (n - 1) / l;
vector <int> ind(n, 0);
iota(ALL(ind), 0);
sort(ALL(ind), [](int i, int j) {
return x[i] < x[j];
});
for (int i = 0; i < n; i++) {
int p = i / l;
int it = ind[i];
pos[it] = mp(p, sz[p]);
b[p][sz[p]++] = it;
}
for (int i = 0; i <= cntb; i++) {
for (int j = 0; j < sz[i]; j++)
v[i][j] = x[b[i][j]];
build(i, b[i], ptr[i], dp[i], v[i]);
}
}
int update(int i, int y) {
cnt++;
del(i);
x[i] = y;
add(i);
int res = 0;
int p = 0;
int cur = 0;
while (true) {
res += dp[p][cur];
cur = ptr[p][cur];
int nxt = p + 1;
while (nxt <= cntb &&
(sz[nxt] == 0 || getmax(nxt) - v[p][cur] <= l))
nxt++;
res++;
if (nxt > cntb)
break;
int lo = -1;
int hi = sz[nxt] - 1;
while (hi - lo > 1) {
int mid = (lo + hi) >> 1;
if (v[nxt][mid] - v[p][cur] <= l)
lo = mid;
else
hi = mid;
}
cur = hi;
p = nxt;
}
if (cnt == Q) {
cnt = 0;
rebuild();
}
return res;
}