#include "bubblesort2.h"
#include <bits/stdc++.h>
#define L(n) (n << 1)
#define R(n) (n << 1 | 1)
using namespace std;
int N, Q;
vector<int> ans, tmp;
map<int, int> id;
set<int, greater<int>> con[1000005];
int tree[4000005];
int lazy[4000005];
void unlazy(int n, int l, int r) {
tree[n] += lazy[n];
if(l != r) {
lazy[L(n)] += lazy[n];
lazy[R(n)] += lazy[n];
}
lazy[n] = 0;
}
void tt(int n, int l, int r) {
unlazy(n, l, r);
if(l == r) {
cout << tree[n] << " ";
return;
}
int mid = (l + r) >> 1;
tt(L(n), l, mid);
tt(R(n), mid + 1, r);
}
void update(int n, int l, int r, int ql, int qr, int val) {
// if(n == 1) cout << "up: "<< ql << " " << qr << " " << val << "\n";
unlazy(n, l, r);
if(qr < l || r < ql) return;
if(ql <= l && r <= qr) {
tree[n] += val;
if(l != r) {
lazy[L(n)] += val;
lazy[R(n)] += val;
}
return;
}
int mid = (l + r) >> 1;
update(L(n), l, mid, ql, qr, val);
update(R(n), mid + 1, r, ql, qr, val);
tree[n] = max(tree[L(n)], tree[R(n)]);
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
N = A.size(), Q = X.size();
ans.resize(Q);
tmp = A;
for(int now : V) tmp.push_back(now);
sort(tmp.begin(), tmp.end());
tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin());
for(int i = 0; i < tmp.size(); i++) {
id[tmp[i]] = i;
// cout << tmp[i] << " ";
}
// cout << "\n";
int mac = tmp.size() - 1, val, pos;
for(int i = 0; i < N; i++) {
val = id[tmp[i]];
update(1, 0, mac, val, mac, -1);
if(con[val].empty()) {
update(1, 0, mac, val, val, i + 1);
}else update(1, 0, mac, val, val, i - *con[val].begin());
con[val].insert(i);
}
// tt(1, 0, mac);
// cout << "\n\n";
for(int i = 0; i < Q; i++) {
pos = X[i], val = id[A[pos]];
if(con[val].size() == 1) update(1, 0, mac, val, val, -pos - 1), con[val].erase(pos);
else if(*con[val].begin() == pos) {
con[val].erase(pos);
update(1, 0, mac, val, val, *con[val].begin() - pos);
}else con[val].erase(pos);
update(1, 0, mac, val, mac, 1);
// tt(1, 0, mac);
// cout << "\n";
A[pos] = V[i];
val = id[A[pos]];
// cout << val << " " << A[pos] << "\n";
if(con[val].empty()) update(1, 0, mac, val, val, pos + 1);
else if(*con[val].begin() < pos) {
update(1, 0, mac, val, val, pos - *con[val].begin());
}
con[val].insert(pos);
update(1, 0, mac, val, mac, -1);
// tt(1, 0, mac);
// cout << "\n\n";
ans[i] = tree[1];
}
return ans;
}
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < tmp.size(); i++) {
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
47488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
47488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
49144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
47488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
