#include "bubblesort2.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace __gnu_pbds;
template<class T> using oset = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;
#define ar array
//~ #define int long long
const int N = 5e5 + 5;
struct Merge_Sort_ST{
oset<int> tree[N * 4];
void erase(int i, int v, int lx = 0, int rx = N, int x = 1){
tree[x].erase(tree[x].upper_bound(v));
if(lx == rx) return;
int m = (lx + rx) >> 1;
if(i <= m) erase(i, v, lx, m, x<<1);
else erase(i, v, m+1, rx, x<<1|1);
}
void insert(int i, int v, int lx = 0, int rx = N, int x = 1){
tree[x].insert(v);
if(lx == rx) return;
int m = (lx + rx) >> 1;
if(i <= m) insert(i, v, lx, m, x<<1);
else insert(i, v, m+1, rx, x<<1|1);
}
int get_big(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return 0;
if(lx >= l && rx <= r) return (int)tree[x].size() - tree[x].order_of_key(v + 1);
int m = (lx + rx) >> 1;
return get_big(l, r, v, lx, m, x<<1) + get_big(l, r, v, m+1, rx, x<<1|1);
}
int get_smol(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return 0;
if(lx >= l && rx <= r) return tree[x].order_of_key(v);
int m = (lx + rx) >> 1;
return get_smol(l, r, v, lx, m, x<<1) + get_smol(l, r, v, m+1, rx, x<<1|1);
}
}tt;
vector<int> countScans(vector<int> a, vector<int> in, vector<int> val){
int n = (int)a.size(), q = (int)in.size();
int res = 0;
for(int i=0;i<n;i++){
//~ cout<<tt.get_big(0, i, a[i])<<"\n";
res += tt.get_big(0, i, a[i]);
tt.insert(i, a[i]);
}
vector<int> rr;
for(int j=0;j<q;j++){
int i = in[j], v = val[j];
res -= tt.get_big(0, i, a[i]);
res -= tt.get_smol(i, n - 1, a[i]);
tt.erase(i, a[i]);
a[i] = v;
tt.insert(i, a[i]);
res += tt.get_big(0, i, a[i]);
res += tt.get_smol(i, n - 1, a[i]);
rr.push_back(res);
} return rr;
}
/*
5 3
1 2 3 4 5
0 3
4 0
3 1
3 2 3 1 0
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
157352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
157352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
372 ms |
182972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
157352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
