#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
int n, l;
vector<int> x;
const int inf = 2'000'000'009;
//const int B = 1600;
const int B = 3;
struct Sqrt {
int n;
vector<int> c, e, x, pBucket;
vector<int> pos;
vector<vector<int>> buckets;
int timer;
int last_buck;
Sqrt() {}
Sqrt(vector<int> _x): x(_x), timer(0) {
n = ssize(x);
c.resize(n);
e.resize(n);
pBucket.resize(n);
last_buck = (n-1)/B;
debug(last_buck);
buckets.resize(last_buck + 1);
vector<int> idx(n);
iota(all(idx), 0);
sort(all(idx), [&](int a, int b) {
return x[a] < x[b];
});
for (int i = 0; i < n; ++i) {
int j = idx[i];
buckets[i/B].eb(j);
pBucket[j] = i/B;
}
for (int i = 0; i <= last_buck; ++i) update_bucket(i);
}
void update_bucket(int idx) {
cerr << "update " << idx << '\n';
int nxt = ssize(buckets[idx]);
for (int i = ssize(buckets[idx])-1; i >= 0; --i) {
// debug(nxt);
while (nxt-1 >= 0 && x[buckets[idx][nxt-1]] > x[buckets[idx][i]] + l) --nxt;
// debug(i);
// debug(buckets[idx][i]);
// debug(nxt);
assert(nxt > i);
c[buckets[idx][i]] = 1 + (nxt < ssize(buckets[idx]) ? c[buckets[idx][nxt]] : 0);
e[buckets[idx][i]] = (nxt < ssize(buckets[idx]) ? e[buckets[idx][nxt]] : x[buckets[idx][i]] + l);
}
}
void update(int i, int y) {
++timer;
auto it = buckets[pBucket[i]].begin();
while (*it != i) ++it;
buckets[pBucket[i]].erase(it);
update_bucket(pBucket[i]);
x[i] = y;
int b;
for (b = 0; b <= last_buck && (buckets[b].empty() || buckets[b].back()) >= y; ++b) ;
if (b > last_buck) --b;
pBucket[i] = b;
buckets[b].eb(i);
int j = ssize(buckets[b]) - 1;
while (j-1 >= 0 && x[buckets[b][j]] < x[buckets[b][j-1]]) {swap(buckets[b][j], buckets[b][j-1]); --j;}
update_bucket(b);
}
int calc_result() {
// int res = c[buckets[0][0]], f = e[buckets[0][0]];
int res = 0, f = -inf;
for (int j = 0; j <= last_buck; ++j) {
debug(res);
debug(f);
if (buckets[j].empty() || f >= x[buckets[j].back()]) continue;
int low = -1, high = ssize(buckets[j]);
while (high-low > 1) {
int mid = (high + low) / 2;
if (x[buckets[j][mid]] > f) high = mid;
else low = mid;
}
res += c[buckets[j][high]];
f = e[buckets[j][high]];
}
return res;
}
void Debug() {
debug(buckets);
debug(x);
debug(c);
debug(e);
}
};
Sqrt q;
void init(int _n, int _l, int _x[]) {
n = _n; l = _l;
for (int i = 0; i < n; ++i) x.eb(_x[i]);
q = Sqrt(x);
q.Debug();
}
int update(int i, int y) {
cerr << "NEW UPDATE \n";
if (q.timer > B) {cerr << "REBUILD \n"; q.Debug(); q = Sqrt(x);}
q.update(i, y);
q.Debug();
return q.calc_result();
}
#ifdef LOCAL
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n, l, m;
cin >> n >> l >> m;
int *x = new int[n];
for (int i = 0; i < n; ++i) cin >> x[i];
init(n, l, x);
for (int i = 0; i < m; ++i) {
// int j, y, s;
// cin >> j >> y >> s;
// int ans = update(j, y);
// cout << "ANS = " << ans << ", expected " << s << '\n';
// if (ans != s) cout << "WA on query " << i+1 << endl;
int j, y;
cin >> j >> y;
cout << update(j, y) << '\n';
}
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
