| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1210391 | Boomyday | Bubble Sort 2 (JOI18_bubblesort2) | C++20 | 0 ms | 0 KiB |
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll BIG = 1e9;
#define int long long
const ll ssz = 1<<20; // 1 << 20
const int INF = 1e9;
vector<int> seg_on(2*ssz, 0);
vector<int> seg_max(2*ssz, -INF), lz_max(2*ssz, 0);
void upd_on(int i, int x){
i += ssz;
seg_on[i] = x;
i /= 2;
while(i >= 1){
seg_on[i] = seg_on[2*i] + seg_on[2*i+1];
i /= 2;
}
}
int quer_on (int l, int r){
if (l > r) return 0;
l += ssz;
r += ssz;
int res = 0;
while(l <= r){
if(l&1) res += seg_on[l++];
if(!(r&1)) res += seg_on[r--];
l /= 2;
r /= 2;
}
return res;
}
void pushdown(int rt, int tl, int tr){
seg_max[rt] += lz_max[rt];
if (tl != tr) {
lz_max[2*rt] += lz_max[rt];
lz_max[2*rt+1] += lz_max[rt];
}
lz_max[rt] = 0;
}
int query(int l, int r, int rt, int tl, int tr){
pushdown(rt, tl, tr);
if (r < tl || l > tr) return -(2*INF);
if (l <= tl && tr <= r) return seg_max[rt];
int mid = (tl + tr) / 2;
return max(query(l, r, 2*rt, tl, mid), query(l, r, 2*rt+1, mid+1, tr));
}
void update(int x, int l, int r, int rt, int tl, int tr){
pushdown(rt, tl, tr);
if (r < tl || l > tr) return;
if (l <= tl && tr <= r) {
lz_max[rt] += x;
pushdown(rt, tl, tr);
return;
}
int mid = (tl + tr) / 2;
update(x, l, r, 2*rt, tl, mid);
update(x, l, r, 2*rt+1, mid+1, tr);
seg_max[rt] = max(seg_max[2*rt], seg_max[2*rt+1]);
}
void point_update(int x, int i){
update(x- query(i, i, 1, 0, ssz-1), i, i, 1, 0, ssz-1);
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
int Q=X.size();
int N = A.size();
vector<int> S(Q);
vector<ll> numvals(N), quervals(Q);
for(int i=0;i<N;++i) numvals[i] = BIG*A[i] + i;
for(int i=0;i<Q;++i) quervals[i] = BIG*V[i] + X[i];
set<ll> compress;
for(int i=0;i<N;++i) compress.insert(numvals[i]);
for(int i=0;i<Q;++i) compress.insert(quervals[i]);
map<ll, int> compress_map;
int idx = 0;
for(auto val : compress) {
compress_map[val] = idx++;
}
for(int i=0;i<N;++i) numvals[i] = compress_map[numvals[i]];
for(int i=0;i<Q;++i) quervals[i] = compress_map[quervals[i]];
for(int i=0;i<N;++i) upd_on(numvals[i], 1);
// output the full segment tree of segon
for(int i=0;i<N;++i){
point_update( i-(quer_on(0, numvals[i]-1)), numvals[i]);
}
// output each value of the segment tree
for(int i=0;i<Q;++i){
if (numvals[X[i]] == quervals[i]){
S[i] = query(0, ssz-1, 1, 0, ssz-1);
continue;
}
// output the numvals array
/*
cout << "numvals: ";
for (int j=0;j<N;++j){
cout << numvals[j] << " ";
}
cout << endl;*/
// newpos = X[i]
// turn off the old value
upd_on(numvals[X[i]],0);
point_update(-INF,numvals[X[i]]);
// update values between old and new
// old value = numvals[X[i]]
// new value = quervals[i]
// if it moves from small to big, add one to the elements
// else subtract one
if (numvals[X[i]] < quervals[i]){
update(1, numvals[X[i]], quervals[i], 1, 0, ssz-1);
}
else if (numvals[X[i]] > quervals[i]){
update(-1, quervals[i], numvals[X[i]], 1, 0, ssz-1);
}
// now update numvals
numvals[X[i]] = quervals[i];
upd_on(quervals[i], 1);
point_update(X[i] - (quer_on(0, quervals[i]-1) ), quervals[i]);
S[i] = query(0, ssz-1, 1, 0, ssz-1);
}
return S;
}
vector<int> countScansSimple(std::vector<int> A, std::vector<int> X, std::vector<int> V){
// count the number of passes it takes to bubblesort A
int Q = X.size();
int N = A.size();
vector<int> S(Q, 0);
vector<int> B = A; // copy of A to sort
for (int i = 0; i < Q; ++i) {
A[X[i]] = V[i]; // update A with the new value
B = A; // reset B to A
int passes = 0;
bool sorted = false;
while (!sorted) {
sorted = true;
for (int j = 0; j < N - 1; ++j) {
if (B[j] > B[j + 1]) {
swap(B[j], B[j + 1]);
sorted = false;
}
}
passes++;
}
S[i] = passes - 1; // subtract 1 because the last pass is not counted
}
return S;
}