#include <bits/stdc++.h>
std::ifstream fin("bubble.in");
std::ofstream fout("bubble.out");
struct Element {
int value, pos, index, norm;
static bool sortByValue(Element &a, Element &b) {
if(a.value == b.value)
return a.pos < b.pos;
return a.value < b.value;
}
static bool sortByIndex(Element &a, Element &b) {
return a.index < b.index;
}
void print() {
fout << value << ' ' << pos << ' ' << index << ' ' << norm << '\n';
}
};
class SegmTree {
int size;
std::vector <int> lazy, min;
void propagate(int node) {
lazy[2*node+1] += lazy[node];
lazy[2*node+2] += lazy[node];
min[2*node+1] += lazy[node];
min[2*node+2] += lazy[node];
lazy[node] = 0;
}
void set(int node, int left, int right, int pos, int value) {
if(left == right) {
min[node] = value;
return;
}
propagate(node);
int mid = (left + right) / 2;
if(mid >= pos)
set(2*node+1, left, mid, pos, value);
else
set(2*node+2, mid+1, right, pos, value);
min[node] = std::min(min[2*node+1], min[2*node+2]);
}
void update(int node, int left, int right, int from, int to, int value) {
if(left > to or right < from)
return;
propagate(node);
if(from <= left and right <= to) {
min[node] += value;
lazy[node] += value;
return;
}
int mid = (left + right) / 2;
update(2*node+1, left, mid, from, to, value);
update(2*node+2, mid+1, right, from, to, value);
min[node] = std::min(min[2*node+1], min[2*node+2]);
}
int query(int node, int left, int right, int from, int to) {
if(left > to or right < from)
return 1e9;
if(from <= left and right <= to)
return min[node];
propagate(node);
int mid = (left + right) / 2;
int ans = std::min(query(2*node+1, left, mid, from, to), query(2*node+2, mid+1, right, from, to));
min[node] = std::min(min[2*node+1], min[2*node+2]);
return ans;
}
public:
SegmTree(int n) {
size = 1;
while(size <= n)
size *= 2;
lazy.resize(2 * size);
min.resize(2 * size);
std::fill(min.begin(), min.end(), 1e9);
}
int getMin() {
return min[0];
}
int querySegm(int left, int right) {
return query(0, 0, size-1, left, right);
}
void updateSegm(int left, int right, int value) {
update(0, 0, size-1, left, right, value);
}
void setSegm(int pos, int value) {
set(0, 0, size-1, pos, value);
}
};
class Bit {
int size;
std::vector <int> bit;
public:
Bit(int n) {
size = n + 1;
bit.resize(size + 1);
}
void update(int pos, int value) {
pos ++;
while(pos <= size) {
bit[pos] += value;
pos = pos + (pos & -pos);
}
}
int query(int pos) {
pos ++;
int ans = 0;
while(pos > 0) {
ans += bit[pos];
pos = pos - (pos & -pos);
}
return ans;
}
};
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
std::vector <int> ans(X.size());
std::vector <Element> v;
int n = A.size();
for(int i = 0, value; i < n; i ++) {
value = A[i];
v.push_back({value, i, i, 0});
}
int Q = X.size();
for(int i = 0, value, pos; i < Q; i ++) {
pos = X[i];
value = V[i];
v.push_back({value, pos, n + i, 0});
}
std::sort(v.begin(), v.end(), Element::sortByValue);
for(int i = 1; i < v.size(); i ++) {
int crt = v[i-1].norm;
if(!(v[i].value == v[i-1].value and v[i].pos == v[i-1].pos))
crt ++;
v[i].norm = crt;
}
std::sort(v.begin(), v.end(), Element::sortByIndex);
SegmTree segm(n+Q);
Bit bit(n+Q);
for(int i = 0; i < n; i ++) {
segm.setSegm(v[i].norm, v[i].pos - i);
bit.update(v[i].norm, 1);
}
for(int i = n; i < n+Q; i ++) {
int currPos = v[v[i].pos].norm;
int nextPos = v[i].norm;
v[v[i].pos].norm = v[i].norm;
segm.setSegm(nextPos, bit.query(nextPos) - v[i].pos);
segm.updateSegm(nextPos + 1, n+Q-1, 1);
segm.updateSegm(currPos + 1, n+Q-1, -1);
segm.setSegm(currPos, 1e9);
// fout << -segm.getMin() << '\n';
ans[i-n] = -segm.getMin();
}
return ans;
}
// int main() {
// int n, Q;
// fin >> n;
// std::vector <int> v(n);
// for(int i = 0; i < n; i ++)
// fin >> v[i];
// fin >> Q;
// std::vector <int> x(Q), val(Q);
// for(int i = 0; i < Q; i ++)
// fin >> x[i] >> val[i];
// std::vector <int> ans = countScans(v, x, val);
// for(auto i: ans)
// fout << i << '\n';
// return 0;
// }
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:169:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Element>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | for(int i = 1; i < v.size(); i ++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
3160 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
