Submission #1159995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159995		AgentPengin	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	6094 ms	123656 KiB

bubblesort2

/**
 *    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)

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40