Submission #1139930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139930		SmuggingSpun	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	6109 ms	123604 KiB

bubblesort2

#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
const int lim = 1e6 + 5;
const int INF = 1e9;
int N, bit[lim], st[lim << 2], lazy[lim << 2];
void update(int p, int x){
	for(; p <= N; p += p & -p){
		bit[p] += x;
	}
}
int get(int p){
	int ans = 0;
	for(; p > 0; p -= p & -p){
		ans += bit[p];
	}
	return ans;
}
void push_down(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 p, int x){
	if(l == r){
		st[id] = x;
		return;
	}
	push_down(id);
	int m = (l + r) >> 1;
	if(m < p){
		update_point(id << 1 | 1, m + 1, r, p, x);
	}
	else{
		update_point(id << 1, l, m, p, x);
	}
	st[id] = max(st[id << 1], st[id << 1 | 1]);
}
void update_range(int id, int l, int r, int u, int v, int x){
	if(l > v || r < u){
		return;
	}
	if(u <= l && v >= r){
		st[id] += x;
		lazy[id] += x;
		return;
	}
	push_down(id);
	int m = (l + r) >> 1;
	update_range(id << 1, l, m, u, v, x);
	update_range(id << 1 | 1, m + 1, r, u, v, x);
	st[id] = max(st[id << 1], st[id << 1 | 1]);
}
vector<int>countScans(vector<int>a, vector<int>x, vector<int>v){
	int n = a.size(), q = x.size();
	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]++;
			}
		}
	}
	else if(n <= 8000 && q <= 8000){
		vector<int>p(n);
		iota(p.begin(), p.end(), 0);
		for(int _i = 0; _i < q; _i++){
			a[x[_i]] = v[_i];
			sort(p.begin(), p.end(), [&] (int i, int j) -> bool{
				return a[i] < a[j] || (a[i] == a[j] && i < j);	
			});
			for(int i = 0; i < n; i++){
				maximize(ans[_i], p[i] - i);
			}
		}
	}
	else if(n <= 50000 && q <= 50000 && *max_element(a.begin(), a.end()) <= 100 && *max_element(v.begin(), v.end()) <= 100){
		vector<set<int>>pos(101);
		for(int i = 0; i < n; i++){
			pos[a[i]].insert(i);
		}
		for(int _i = 0; _i < q; _i++){
			pos[a[x[_i]]].erase(x[_i]);
			pos[a[x[_i]] = v[_i]].insert(x[_i]);
			for(int i = 1, cnt = 0; i < 101; i++){
				if(!pos[i].empty()){
					maximize(ans[_i], *pos[i].rbegin() - (cnt += pos[i].size()) + 1);
				}
			} 
		}		
	}
	else{
		vector<int>compress = a;
		for(int& x : v){
			compress.emplace_back(x);
		}
		sort(compress.begin(), compress.end());
		compress.resize(unique(compress.begin(), compress.end()) - compress.begin());
		vector<set<int>>pos((N = compress.size()) + 1);
		memset(bit, 0, sizeof(bit));
		for(int i = 0; i < n; i++){
			pos[a[i] = lower_bound(compress.begin(), compress.end(), a[i]) - compress.begin() + 1].insert(i);
			update(a[i], 1);
		}
		memset(st, -0x3f, sizeof(st));
		memset(lazy, 0, sizeof(lazy));
		for(int i = 1, cnt = 0; i <= N; i++){
			if(!pos[i].empty()){
				update_point(1, 1, N, i, *pos[i].rbegin() - (cnt += pos[i].size()) + 1); 
			}
		}
		for(int _i = 0; _i < q; _i++){
			if((v[_i] = lower_bound(compress.begin(), compress.end(), v[_i]) - compress.begin() + 1) > a[x[_i]] + 1){
				update_range(1, 1, N, a[x[_i]] + 1, v[_i] - 1, 1);
			}
			else if(v[_i] < a[x[_i]] - 1){
				update_range(1, 1, N, v[_i] + 1, a[x[_i]] - 1, -1);
			}
			pos[a[x[_i]]].erase(x[_i]);
			update(a[x[_i]], -1);
			update(v[_i], 1);
			if(!pos[a[x[_i]]].empty()){
				update_point(1, 1, N, a[x[_i]], *pos[a[x[_i]]].rbegin() - get(a[x[_i]]) + 1);
			}
			else{
				update_point(1, 1, N, a[x[_i]], -INF);
			}
			pos[a[x[_i]] = v[_i]].insert(x[_i]);
			update_point(1, 1, N, v[_i], *pos[v[_i]].rbegin() - get(v[_i]) + 1);
			ans[_i] = st[1];
		}
	}
	return ans;
}

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