| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1159994 | AgentPengin | Bubble Sort 2 (JOI18_bubblesort2) | C++20 | 0 ms | 0 KiB |
/**
* author: AgentPengin ( Độc cô cầu bại )
* created: 23.12.2022 10:08:02
* too lazy to update time
**/
#include<bits/stdc++.h>
// #include"bubblesort2.h"
#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)
using namespace std;
const ll mod = 1e9 + 7;
const int inf = 1e9;
const int MAXN = 1e6 + 5;
int N, bit[MAXN], st[MAXN << 2], lazy[MAXN << 2];
void update(int x, int val) {
for (;x <= N; x += x&-x) bit[x] += val;
}
int get(int x) {
int ans = 0;
for (;x;x-=x&-x) ans += bit[x];
return ans;
}
void pushDown(int id) {
st[id << 1] += lazy[id];
lazy[id << 1] += lazy[id];
st[id << 1 | 1] += lazy[id];
lazy[id << 1 | 1] += lazy[id];
lazy[id] = 0;
}
void update_point(int id, int l,int r, int pos, int val) {
if (l == r) {
st[id] = val;
return;
}
pushDown(id);
int mid = l + r >> 1;
if (pos <= mid) {
update_point(id << 1,l , mid, pos, val);
} else {
update_point(id << 1 | 1,mid + 1, r, pos, val);
}
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
void update_range(int id, int l, int r, int u, int v, int val) {
if (v < l || u > r) return;
if (u <= l && r <= v) {
st[id] += val;
lazy[id] += val;
return;
}
pushDown(id);
int mid = l + r >> 1;
update_range(id << 1, l, mid, u, v, val);
update_range(id << 1 | 1,mid + 1, r, u, v, val);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
int n = sz(a), q = sz(x);
vector<int> ans(q, 0);
if (n <= 2000 && q <= 2000) {
for (int i = 0;i < q;i++) {
a[x[i]] = v[i];
vector<int> A = a;
while(true) {
bool swapped = false;
for (int i = 1;i < n;i++) {
if (A[i - 1] > A[i]) {
swap(A[i - 1], A[i]);
swapped = true;
}
}
if (!swapped) break;
ans[i]++;
}
}
return ans;
} else if (n <= 8000 && q <= 8000) {
vector<int> p(n);
iota(bend(p), 0);
for (int i = 0;i < q;i++) {
a[x[i]] = v[i];
sort(bend(p), [&](int u, int v){
return a[u] < a[v] || (a[u] == a[v] && u < v);
});
for (int j = 0;j < n;j++) {
ans[i] = max(ans[i], p[j] - j);
}
}
return ans;
} else if (n <= 50000 && q <= 50000 && *max_element(bend(a)) <= 100 && *max_element(bend(v)) <= 100) {
vector<set<int>> pp(101);
for (int i = 0;i < n;i++) pp[a[i]].insert(i);
for (int i = 0;i < q;i++) {
pp[a[x[i]]].erase(x[i]);
pp[a[x[i]] = v[i]].insert(x[i]);
for (int j = 1, cnt = 0;j < 101;j++) {
if (!pp[j].empty()) {
ans[i] = max(ans[i],*pp[j].rbegin() - (cnt += sz(pp[j])) + 1);
}
}
}
return ans;
} else {
vector<int> compress = a;
for (auto x : v) compress.push_back(x);
sort(bend(compress));
compress.resize(unique(bend(compress)) - compress.begin());
vector<set<int>> pos((N = sz(compress)) + 1);
memset(bit, 0, sizeof bit);
memset(st, -0x3f, sizeof st);
memset(lazy, 0, sizeof lazy);
for (int i = 0;i < n;i++) {
pos[a[i] = lower_bound(bend(compress), a[i]) - compress.begin() + 1].insert(i);
update(a[i], 1);
}
for (int i = 1, cnt = 0;i <= N;i++) {
if (!pos[i].empty()) {
update_point(1, 1, N, i, *pos[i].rbegin() - (cnt += sz(pos[i])) + 1);
}
}
for (int _ = 0;_ < q;_++) {
if ((v[_] = lower_bound(bend(compress), v[_]) - compress.begin() + 1) > a[x[_]] + 1) {
update_range(1, 1, N, a[x[_]] + 1, v[_] - 1, 1);
} else if (v[_] < a[x[_]] - 1) {
update_range(1, 1, N, v[_] + 1, a[x[_]] - 1, -1);
}
pos[a[x[_]]].erase(x[_]);
update(a[x[_]], -1);
update(v[_], 1);
if (!pos[a[x[_]]].empty()) {
update_point(1, 1, N, a[x[_]], *pos[a[x[_]]].rbegin() - get(a[x[_]]) + 1);
} else {
update_point(1, 1, N, a[x[_]], -inf);
}
pos[a[x[_]] = v[_]].insert(x[_]);
update_point(1, 1, N, v[_], *pos[v[_]].rbegin() - get(v[_]) + 1);
ans[_] = st[1];
}
return ans;
}
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
if (ifstream(NAME".inp")) {
freopen(NAME".inp","r",stdin);
freopen(NAME".out","w",stdout);
}
vector<int> a = {1, 2, 3, 4};
vector<int> x = {0, 2};
vector<int> v = {3, 1};
vector<int> ans = countScans(a, x, v);
for (auto x : ans) cout << x << '\n';
cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
// agent pengin wants to take apio (with anya-san)