Submission #1305609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305609		peteza	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	2523 ms	115892 KiB

bubblesort2

//little anger, how blessing to be capable of fireeee
#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
using ll = long long;
const ll rinf = -2000000000ll;
const ll ninf = -2003000000ll;
 
int aq;
vector<pair<int, int>> qrss;
ll laz[4000005], segm[4000005], segs[4000005];
 
void plaz(int idx, int cnt) {
	segm[idx] += laz[idx];
	if(cnt > 1) {
		laz[idx*2+1] += laz[idx];
		laz[idx*2+2] += laz[idx];
	}
	laz[idx]=0;
}
 
void updset(int idx, int l, int r, int tgt, int val) {
	plaz(idx, r-l+1);
	if(l == r) {
		segm[idx] = val;
		segs[idx] = (val > rinf);
		return;
	}
	int mid = (l+r) >> 1;
	if(tgt <= mid) updset(idx*2+1, l, mid, tgt, val);
	else updset(idx*2+2, mid+1, r, tgt, val);
	plaz(idx*2+1, mid-l+1); plaz(idx*2+2, r-mid);
	segm[idx] = max(segm[idx*2+1], segm[idx*2+2]);
	//printf("Set segm[%d] = %lld\n", idx, segm[idx]);
	//printf("It's from %lld and %lld\n", segm[idx*2+1], segm[idx*2+2]);
	segs[idx] = segs[idx*2+1] + segs[idx*2+2];
}
 
void updrng(int idx, int l, int r, int tl, int tr, int val) {
	plaz(idx, r-l+1);
	if(tl <= l && r <= tr) {
		laz[idx] += val;
		plaz(idx, r-l+1);
		//cout << "INstant " << idx << " -> " << segm[idx] << '\n';
		return;
	}
	if(tr < l || r < tl) return ;
	int mid = (l+r) >> 1;
	updrng(idx*2+1, l, mid, tl, tr, val);
	updrng(idx*2+2, mid+1, r, tl, tr, val);
	segm[idx] = max(segm[idx*2+1], segm[idx*2+2]);
	//printf("Set segm[%d] = %lld\n", idx, segm[idx]);
	//printf("It's from %lld and %lld\n", segm[idx*2+1], segm[idx*2+2]);
}
 
ll qrs(int idx, int l, int r, int tl, int tr) {
	plaz(idx, r-l+1);
	if(tl <= l && r <= tr) return segs[idx];
	if(r < tl || tr < l) return 0;
	int mid = (l+r) >> 1;
	return qrs(idx*2+1, l, mid, tl, tr) + qrs(idx*2+2, mid+1, r, tl, tr);
}
 
ll qrm(int idx, int l, int r, int tl, int tr) {
	plaz(idx, r-l+1);
	if(tl <= l && r <= tr) return segm[idx];
	if(r < tl || tr < l) return ninf;
	int mid = (l+r) >> 1;
	return max(qrm(idx*2+1, l, mid, tl, tr), qrm(idx*2+2, mid+1, r, tl, tr));
}
 
void addElem(int x, int v) {
	//assumes element is currently not there
	auto idx = lower_bound(qrss.begin(), qrss.end(), make_pair(v, x)) - qrss.begin();
	assert(qrss[idx] == make_pair(v, x));
	int bfs = qrs(0, 0, aq, 0, idx);
	//cout << "HEYHEY IM ADDINGHEYYYYYYYYYYYY\n";
	updrng(0, 0, aq, idx, aq, -1);
	//cout << "im adding -1 to " << idx << " til " << aq << '\n';
	updset(0, 0, aq, idx, x-bfs);
}
 
void delElem(int x, int v) {
	//assumes element is there
	auto idx = lower_bound(qrss.begin(), qrss.end(), make_pair(v, x)) - qrss.begin();
	assert(qrss[idx] == make_pair(v, x));
	updset(0, 0, aq, idx, ninf);
	int bfs = qrs(0, 0, aq, 0, idx);
	updrng(0, 0, aq, idx, aq, 1);
	//cout << "im adding 1 to " << idx << " til " << aq << '\n';
}
 
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
	int n = A.size(), q = X.size();
	//vector<pair<int, int>> qrs;
	qrss.clear();
	for(int i=0;i<n;i++) qrss.emplace_back(A[i], i);
	for(int i=0;i<q;i++) qrss.emplace_back(V[i], X[i]);
	sort(qrss.begin(), qrss.end());
	qrss.resize(unique(qrss.begin(), qrss.end()) - qrss.begin());
	aq = qrss.size();
	for(int i=0;i<=4*aq;i++) {
		segm[i] = ninf;
		laz[i] = segs[i] = 0;
	}
	for(int i=0;i<n;i++) {
		addElem(i, A[i]);
	}
	//cout << segm[0] << "___"; for(int i=0;i<=aq;i++) cout << qrm(0, 0, aq, i, i) << ' '; cout << '\n';
	vector<int> ans(q);
	for(int i=0;i<q;i++) {
		delElem(X[i], A[X[i]]);
		A[X[i]]=V[i];
		addElem(X[i], A[X[i]]);
		//cout << segm[0] << "___";
		ans[i] = max(0ll, qrm(0, 0, aq, 0, aq));
		//for(int i=0;i<=aq;i++) cout << qrm(0, 0, aq, i, i) << ' ';
		//cout << '\n';
	}
	return ans;
}
 
/*
int main() {
	// your code goes here
	//auto res = countScans({1,2,3,4},{0,2},{3,1});
	auto res = countScans({1,2,3,4},{0,2},{0,1});
	for(auto&e:res) cout << e << " ";
	return 0;
}*/

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