#include "bubblesort2.h"
#include "bits/stdc++.h"
using namespace std;
map<int,int> compress;
int n = 1;
struct segment_tree{
int t[1'000'001 * 3], lz[1'000'001 * 3];
void build(int l = 0, int r = n - 1, int k = 1){
if (l == r){
t[k] = 0;
lz[k] = 0;
return;
}
build(l,(l+r)/2,k*2);
build((l+r)/2+1,r,k*2+1);
t[k] = 0;
lz[k] = 0;
}
void push(int k, int l, int r){
t[k] += lz[k];
if (l != r){
lz[k * 2] += lz[k];
lz[k * 2 + 1] += lz[k];
}
lz[k] = 0;
}
void upd(int l, int r, int k, int L, int R, int V){
//cout << l << " " << r << " " << L << " " << R << " " << V << endl;
push(k,l,r);
if (l > R || r < L)return;
if (l >= L && r <= R){
lz[k] += V;
push(k,l,r);
return;
}
int mid = (l+r) / 2;
upd(l,mid,k*2,L,R,V);
upd(mid+1,r,k*2+1,L,R,V);
t[k] = max(t[k * 2], t[k * 2 + 1]);
}
int get(int W, int l = 0, int r = n - 1, int k = 1){
push(k,l,r);
if (l == r){
return t[k];
}
int mid = (l+r)/2;
if (W <= mid)return get(W,l,mid,k*2);
else return get(W,mid+1,r,k*2+1);
}
} st;
vector<int> countScans(vector<int> A, vector<int> X,vector<int> V){
int Q = X.size();
vector<int> answer(Q);
vector<int> AllElements;
for (int i = 0; i < (int)A.size(); i++)AllElements.push_back(A[i]);
for (int i = 0; i < (int)V.size(); i++)AllElements.push_back(V[i]);
sort(AllElements.begin(), AllElements.end());
AllElements.erase(unique(AllElements.begin(), AllElements.end()), AllElements.end());
for (int i = 0; i < (int)AllElements.size(); i++) compress[AllElements[i]] = i;
n = (int) AllElements.size();
st.build();
for (int i = 0; i < (int)A.size(); i++){
st.upd(0,n-1,1,compress[A[i]],n - 1, -1);
st.upd(0,n-1,1,compress[A[i]], compress[A[i]], i + 1);
//for (int j = 0; j < n; j++)cout << st.get(j) << ' ';
//cout << endl;
}
for (int i = 0; i < (int)X.size(); i++){
st.upd(0,n-1,1,compress[A[X[i]]], n - 1, 1);
st.upd(0,n-1,1,compress[A[X[i]]], compress[A[X[i]]], -X[i] - 1);
A[X[i]] = V[i];
st.upd(0,n-1,1,compress[A[i]],n - 1, -1);
st.upd(0,n-1,1,compress[A[i]], compress[A[i]], i + 1);
st.push(1,0,n-1);
answer[i] = st.t[1];
}
return answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
2904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
