#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 int log2_ceil(int n) {
int i = 0;
while ((1 << i) < n) i++;
return i;
}
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;
}
const int NMAX = 1 << log2_ceil(5e5);
int n, q;
int a[NMAX];
vector<ordered_tree<pair<int, int>>> cox;
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v){
n = (int)a.size();
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(current_index.begin(), current_index.end(), val);
};
int squirt = sqrt_ceil(n);
cox = vector<ordered_tree<pair<int, int>>>(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++;
}
vector<int> answer(q);
for (int j = 0; j < q; j++) {
int cnt = 0;
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;
}
return answer;
}
/*
int main() {
#ifdef LOCAL
freopen("file.in", "r", stdin);
#endif
int n, q;
cin >> n >> q;
vector<int> a(n), x(q), v(q);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < q; i++) cin >> x[i] >> v[i];
for (int r : countScans(a, x, v)) cout << r << '\n';
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
2652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
