#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 150005;
const int BLOCK = 390;
ii sorted_pos[MAXN], bel[MAXN];
int id[BLOCK][2 * BLOCK], dp[BLOCK][2 * BLOCK];
int pos_block[BLOCK][2 * BLOCK], nxt[BLOCK][2 * BLOCK];
int pos[MAXN], block_size[MAXN], nArr, numBlock, maxLen;
void build(void) {
for (int i = 0; i < nArr; ++i)
sorted_pos[i] = ii(pos[i], i);
sort(sorted_pos, sorted_pos + nArr);
numBlock = (nArr + BLOCK - 1) / BLOCK;
for (int i = 0; i < numBlock; ++i) {
block_size[i] = min(nArr, (i + 1) * BLOCK - 1) - i * BLOCK;
int k(block_size[i] - 1);
for (int j = k; j >= 0; --j) {
pos_block[i][j] = sorted_pos[i * BLOCK + j].fi;
while(j < k && pos_block[i][j] + maxLen < pos_block[i][k - 1])
--k;
id[i][j] = sorted_pos[i * BLOCK + j].se;
bel[sorted_pos[i * BLOCK + j].se] = {i, j};
if(pos_block[i][j] + maxLen >= pos_block[i][block_size[i] - 1]) {
nxt[i][j] = pos_block[i][j] + maxLen;
dp[i][j] = 1;
} else {
nxt[i][j] = nxt[i][k];
dp[i][j] = 1 + dp[i][k];
}
}
}
}
void rebuildBlock(int i) {
int k(block_size[i] - 1);
for (int j = k; j >= 0; --j) {
while(j + 1 < k && pos_block[i][j] + maxLen < pos_block[i][k - 1])
--k;
if(pos_block[i][j] + maxLen >= pos_block[i][block_size[i] - 1]) {
nxt[i][j] = pos_block[i][j] + maxLen;
dp[i][j] = 1;
} else {
nxt[i][j] = nxt[i][k];
dp[i][j] = 1 + dp[i][k];
}
}
}
int query(void) {
int res(0), lst(-1);
for (int i = 0; i < numBlock; ++i) {
int p = upper_bound(pos_block[i], pos_block[i] + block_size[i], lst) - pos_block[i];
if(p < block_size[i]) {
res += dp[i][p];
lst = nxt[i][p];
}
}
return res;
}
int update(int u, int newPos) {
pos[u] = newPos;
ii x(bel[u]);
/*for (int j = 0; j < block_size[x.fi]; ++j)
cout << pos_block[x.fi][j] << ' '; cout << '\n';
for (int j = 0; j < block_size[x.fi]; ++j)
cout << id[x.fi][j] << ' '; cout << '\n';
for (int j = 0; j < block_size[x.fi]; ++j)
cout << bel[id[x.fi][j]].se << ' '; cout << '\n';*/
for (int i = x.se + 1; i < block_size[x.fi]; ++i) {
pos_block[x.fi][i - 1] = pos_block[x.fi][i];
id[x.fi][i - 1] = id[x.fi][i];
--bel[id[x.fi][i - 1]].se;
}
--block_size[x.fi];
rebuildBlock(x.fi);
ii y = ii(numBlock - 1, block_size[numBlock - 1]);
for (int i = 0; i < numBlock; ++i) {
if(newPos <= pos_block[i][block_size[i] - 1]) {
int j = upper_bound(pos_block[i], pos_block[i] + block_size[i], newPos) - pos_block[i];
y = {i, j};
break;
}
}
assert(y.fi >= 0);
for (int i = block_size[y.fi]; i > y.se; --i) {
pos_block[y.fi][i] = pos_block[y.fi][i - 1];
id[y.fi][i] = id[y.fi][i - 1];
++bel[id[y.fi][i]].se;
}
++block_size[y.fi];
/*cout << y.fi << ' ' << y.se << ": ";
for (int j = 0; j < block_size[y.fi]; ++j)
cout << pos_block[x.fi][j] << ' '; cout << '\n';
for (int j = 0; j < block_size[y.fi]; ++j)
cout << id[x.fi][j] << ' '; cout << '\n';
for (int j = 0; j < block_size[y.fi]; ++j)
cout << bel[id[x.fi][j]].se << ' '; cout << '\n';*/
pos_block[y.fi][y.se] = newPos;
bel[u] = ii(y.fi, y.se);
id[y.fi][y.se] = u;
rebuildBlock(y.fi);
if(block_size[x.fi] == 0 || block_size[y.fi] >= 2 * BLOCK)
build();
return query();
}
void init(int _N, int _L, int _X[]) {
nArr = _N, maxLen = _L;
for (int i = 0; i < nArr; ++i)
pos[i] = _X[i];
build();
}
#ifdef Nhoksocqt1
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TASK "ioi11_elephants"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
int *X, n, L;
cin >> n >> L;
X = new int[n + 1];
for (int i = 0; i < n; ++i)
cin >> X[i];
init(n, L, X);
int q;
cin >> q;
for (int t = 0; t < q; ++t) {
int i, y;
cin >> i >> y;
cout << update(i, y) << '\n';
}
return 0;
}
#endif // Nhoksocqt1
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14680 KB |
Output is correct |
| 2 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 3 |
Correct |
2 ms |
14684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14680 KB |
Output is correct |
| 2 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 3 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 4 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 5 |
Correct |
2 ms |
14808 KB |
Output is correct |
| 6 |
Correct |
2 ms |
14680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14680 KB |
Output is correct |
| 2 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 3 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 4 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 5 |
Correct |
2 ms |
14808 KB |
Output is correct |
| 6 |
Correct |
2 ms |
14680 KB |
Output is correct |
| 7 |
Incorrect |
13 ms |
17752 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14680 KB |
Output is correct |
| 2 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 3 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 4 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 5 |
Correct |
2 ms |
14808 KB |
Output is correct |
| 6 |
Correct |
2 ms |
14680 KB |
Output is correct |
| 7 |
Incorrect |
13 ms |
17752 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14680 KB |
Output is correct |
| 2 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 3 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 4 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 5 |
Correct |
2 ms |
14808 KB |
Output is correct |
| 6 |
Correct |
2 ms |
14680 KB |
Output is correct |
| 7 |
Incorrect |
13 ms |
17752 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
