#include "elephants.h"
#include "bits/stdc++.h"
using namespace std;
const int B = 200;
const int LOG = 18;
const int N = 150003;
const int INF = 1e9 + 7;
int n, l, qc;
int nx[LOG][N];
bool is_changed[N];
map<int, int> to_val;
set<int> min_changed_val;
multiset<pair<int, int>> se;
vector<pair<int, int>> changed;
void rebuild() {
qc = 0;
vector<pair<int, int>> a;
for (int i = 0; i < n; ++i) {
is_changed[i] = false;
a.emplace_back(to_val[i], i);
}
se.clear();
changed.clear();
min_changed_val.clear();
sort(a.begin(), a.end());
int r = n - 1;
for (int i = n - 1; i >= 0; --i) {
while (r > i && a[r].first - a[i].first > l) {
r--;
}
nx[0][a[i].second] = (r + 1 == n ? n : a[r + 1].second);
se.emplace(a[i]);
}
for (int j = 1; j < LOG; ++j) {
for (int i = 0; i < n; ++i) {
nx[j][i] = (nx[j - 1][i] == n ? n : nx[j - 1][nx[j - 1][i]]);
}
}
}
void edit(int i, int v) {
if (is_changed[i]) {
for (int j = 0; j < (int) changed.size(); ++j) {
if (changed[j].second == i) {
changed.erase(changed.begin() + j);
break;
}
}
} else {
se.erase(se.find({to_val[i], i}));
}
bool f = false;
for (int j = 0; j < (int) changed.size(); ++j) {
if (changed[j].first > v) {
changed.insert(changed.begin() + j, {v, i});
f = true;
break;
}
}
if (!f) {
changed.emplace_back(v, i);
}
min_changed_val.insert(to_val[i]);
to_val[i] = v;
min_changed_val.insert(v);
is_changed[i] = true;
}
void init(int N_, int L, int X[]) {
n = N_, l = L;
for (int i = 0; i < n; ++i) {
to_val[i] = X[i];
}
rebuild();
}
int update(int i, int y) {
edit(i, y);
qc++;
if (qc == B) {
rebuild();
}
int x = -1, ptr = 0, ans = 0;
while (true) {
pair<int, int> key = {x, INF};
auto it = se.upper_bound(key);
int c = INF, ind = n;
if (it != se.end()) {
c = it->first, ind = it->second;
}
int d = INF;
if (ptr < (int) changed.size()) {
d = changed[ptr].first;
}
if (c == INF && d == INF) {
break;
}
if (c < d) {
int above = INF;
auto it2 = min_changed_val.lower_bound(c);
if (it2 != min_changed_val.end()) {
above = *it2;
assert(above <= d);
}
for (int b = LOG - 1; b >= 0; --b) {
if (!is_changed[nx[b][ind]] && nx[b][ind] < n && to_val[nx[b][ind]] < above) {
c = to_val[nx[b][ind]], ind = nx[b][ind], ans += 1 << b;
}
}
ans++;
x = max(c + l, above - 1);
} else {
ans++;
x = d + l;
}
while (ptr < (int) changed.size() && changed[ptr].first <= x) {
ptr++;
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
18776 KB |
Output is correct |
2 |
Correct |
2 ms |
18780 KB |
Output is correct |
3 |
Correct |
2 ms |
18780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
18776 KB |
Output is correct |
2 |
Correct |
2 ms |
18780 KB |
Output is correct |
3 |
Correct |
2 ms |
18780 KB |
Output is correct |
4 |
Correct |
2 ms |
18780 KB |
Output is correct |
5 |
Correct |
3 ms |
18780 KB |
Output is correct |
6 |
Correct |
2 ms |
18780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
18776 KB |
Output is correct |
2 |
Correct |
2 ms |
18780 KB |
Output is correct |
3 |
Correct |
2 ms |
18780 KB |
Output is correct |
4 |
Correct |
2 ms |
18780 KB |
Output is correct |
5 |
Correct |
3 ms |
18780 KB |
Output is correct |
6 |
Correct |
2 ms |
18780 KB |
Output is correct |
7 |
Correct |
607 ms |
22628 KB |
Output is correct |
8 |
Correct |
816 ms |
23176 KB |
Output is correct |
9 |
Correct |
7125 ms |
26956 KB |
Output is correct |
10 |
Correct |
2626 ms |
28116 KB |
Output is correct |
11 |
Correct |
2597 ms |
28464 KB |
Output is correct |
12 |
Execution timed out |
9026 ms |
28464 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
18776 KB |
Output is correct |
2 |
Correct |
2 ms |
18780 KB |
Output is correct |
3 |
Correct |
2 ms |
18780 KB |
Output is correct |
4 |
Correct |
2 ms |
18780 KB |
Output is correct |
5 |
Correct |
3 ms |
18780 KB |
Output is correct |
6 |
Correct |
2 ms |
18780 KB |
Output is correct |
7 |
Correct |
607 ms |
22628 KB |
Output is correct |
8 |
Correct |
816 ms |
23176 KB |
Output is correct |
9 |
Correct |
7125 ms |
26956 KB |
Output is correct |
10 |
Correct |
2626 ms |
28116 KB |
Output is correct |
11 |
Correct |
2597 ms |
28464 KB |
Output is correct |
12 |
Execution timed out |
9026 ms |
28464 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
18776 KB |
Output is correct |
2 |
Correct |
2 ms |
18780 KB |
Output is correct |
3 |
Correct |
2 ms |
18780 KB |
Output is correct |
4 |
Correct |
2 ms |
18780 KB |
Output is correct |
5 |
Correct |
3 ms |
18780 KB |
Output is correct |
6 |
Correct |
2 ms |
18780 KB |
Output is correct |
7 |
Correct |
607 ms |
22628 KB |
Output is correct |
8 |
Correct |
816 ms |
23176 KB |
Output is correct |
9 |
Correct |
7125 ms |
26956 KB |
Output is correct |
10 |
Correct |
2626 ms |
28116 KB |
Output is correct |
11 |
Correct |
2597 ms |
28464 KB |
Output is correct |
12 |
Execution timed out |
9026 ms |
28464 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |