#include "./bubblesort2.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <climits>
using namespace std;
namespace pbds = __gnu_pbds;
template<typename T>
using ordered_tree = pbds::tree<T, pbds::null_type, less<T>, pbds::rb_tree_tag, pbds::tree_order_statistics_node_update>;
constexpr long long sqrt_ceil(long long n) {
long long b = 1, e = n;
while (b < e) {
long long m = (b + e) / 2;
if (m * m < n) b = m + 1;
else e = m;
}
return b;
}
int lsb(int n) {
return 1 << __builtin_ctz(n);
}
struct Aib {
int n;
vector<int> aib;
void add(int v, int i) {
while (i <= n) {
aib[i] += v;
i += lsb(i);
}
}
int sum(int i) {
int s = 0;
while (i > 0) {
s += aib[i];
i -= lsb(i);
}
return s;
}
Aib(int n) {
this->n = n;
aib = vector<int>(n + 1);
}
};
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v){
int n = (int)a.size();
int q = (int)x.size();
vector<int> s(n + q);
copy(a.begin(), a.end(), s.begin());
copy(v.begin(), v.end(), s.begin() + n);
sort(s.begin(), s.end());
s.resize(unique(s.begin(), s.end()) - s.begin());
vector<int> current_index(s.size());
vector<int> id(n);
auto get_id = [&](int val)->int& {
return *lower_bound(s.begin(), s.end(), val);
};
int squirt = n;
vector<ordered_tree<pair<int, int>>> cox(squirt);
for (int i = 0; i < n; i++) {
int& curr_id = get_id(a[i]);
cox[i / squirt].insert({a[i], curr_id});
id[i] = curr_id;
curr_id++;
}
long long prev = 0;
{
Aib aib(s.size());
for (int i = 0; i < n; i++) {
int idd = get_id(a[i]);
prev += aib.sum(idd);
aib.add(1, idd+1);
}
}
vector<int> answer(q);
for (int j = 0; j < q; j++) {
int cnt = 0;
for (int i = 0; i < n; i++) {
cnt -= i < x[j] && a[i] > a[x[j]];
cnt -= i > x[j] && a[i] < a[x[j]];
cnt += i < x[j] && a[i] > v[j];
cnt += i > x[j] && a[i] < v[j];
}
answer[j] = cnt;
a[x[j]] = v[j];
continue;
int laba = x[j] / squirt;
for (int i = 0; i < laba; i++) cnt -= (int)cox[i].size() - (int)cox[i].order_of_key({a[x[j]], INT_MAX});
for (int i = laba + 1; i < (int)cox.size(); i++) cnt -= (int)cox[i].order_of_key({a[x[j]], 0});
for (int i = 0; i < laba; i++) cnt += (int)cox[i].size() - (int)cox[i].order_of_key({v[j], INT_MAX});
for (int i = laba + 1; i < (int)cox.size(); i++) cnt += (int)cox[i].order_of_key({v[j], 0});
for (int i = laba * squirt; i < min(n, (laba + 1) * squirt); i++) {
cnt -= i < x[j] && a[i] > a[x[j]];
cnt -= i > x[j] && a[i] < a[x[j]];
cnt += i < x[j] && a[i] > v[j];
cnt += i > x[j] && a[i] < v[j];
}
cox[laba].erase(cox[laba].lower_bound({a[x[j]], 0}));
int& curr_id = get_id(v[j]);
cox[laba].insert({v[j], curr_id});
id[x[j]] = curr_id;
curr_id++;
answer[j] = cnt;
a[x[j]] = v[j];
}
return answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
88 ms |
5212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
