#include "bits/stdc++.h"
#include "bubblesort2.h"
using namespace std;
const int maxn = 1000010;
int t[4 * maxn], prop[4 * maxn], opt[maxn], pre[maxn];
set <int> cont[maxn];
int idx;
void pushdown(int c) {
if(!prop[c]) return ;
int l = c << 1;
int r = l + 1;
t[l] += prop[c]; t[r] += prop[c];
prop[l] += prop[c]; prop[r] += prop[c];
prop[c] = 0;
}
void add(int x, int y, int val, int c = 1, int b = 1, int e = idx) {
if(x <= b && e <= y) {
t[c] += val;
prop[c] += val;
return ;
}
if(y < b || e < x) return ;
pushdown(c);
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
add(x, y, val, l, b, m);
add(x, y, val, r, m + 1, e);
t[c] = max(t[l], t[r]);
}
inline int getMin() {
return max(0, t[1]);
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
vector <int> answer (X.size());
map <int, int> cmp;
for(int i = 0; i < A.size(); i++) cmp[A[i]];
for(int i = 0; i < V.size(); i++) cmp[V[i]];
idx = 0;
for(auto &i : cmp) {
i.second = ++idx;
pre[idx] = t[idx] = opt[idx] = 0;
cont[idx].clear();
}
for(int i = 0; i < A.size(); i++) {
A[i] = cmp[A[i]];
pre[A[i]] += 1;
opt[A[i]] = i + 1;
cont[A[i]].insert(i + 1);
}
for(int i = 1; i <= idx; i++) {
pre[i] += pre[i - 1];
t[i] = opt[i] - pre[i];
cont[i].insert(0);
}
for(int i = 0; i < V.size(); i++) {
int x = X[i];
int tmp;
V[i] = cmp[V[i]];
add(A[x], idx, 1);
cont[A[x]].erase(x + 1);
tmp = opt[A[x]];
opt[A[x]] = *cont[A[x]].rbegin();
add(A[x], A[x], opt[A[x]] - tmp);
A[x] = V[i];
add(A[x], idx, -1);
cont[A[x]].insert(x + 1);
tmp = opt[A[x]];
opt[A[x]] = *cont[A[x]].rbegin();
add(A[x], A[x], opt[A[x]] - tmp);
answer[i] = getMin();
}
return answer;
}
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:38:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < A.size(); i++) cmp[A[i]];
~~^~~~~~~~~~
bubblesort2.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < V.size(); i++) cmp[V[i]];
~~^~~~~~~~~~
bubblesort2.cpp:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < A.size(); i++) {
~~^~~~~~~~~~
bubblesort2.cpp:57:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < V.size(); i++) {
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
47480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
47480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
48888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
47480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
