Submission #1262054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262054		shafi_root	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	1274 ms	36528 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define pii pair<int, int>
// #define F first
// #define S second
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)

const int MXN = 1e6+5;

int n, q, seg[MXN<<2], lz[MXN<<2];

void Put(int x, int id) {
	seg[id] += x;
	lz[id] += x;
}

void Shift(int l, int r, int id) {
	if (r - l > 1 && lz[id]) {
		Put(lz[id], lc);
		Put(lz[id], rc);
		lz[id] = 0;
	}
}

void Upd(int s, int e, int x, int l = 0, int r = MXN, int id=1) {
	Shift(l, r, id);
	if (s <= l && r <= e) {
		Put(x, id);
		return;
	}
	if (s < mid) Upd(s,e,x, l, mid, lc);
	if (mid < e) Upd(s,e,x, mid, r, rc);
	seg[id] = max(seg[lc], seg[rc]);
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	q=X.size();
	n = A.size();
	vector<pii> vec;
	for(int i=0;i<n;i++) {
		vec.pb({A[i], i});
	}
	
	for(int j=0;j<q;j++) {
		vec.pb({V[j], X[j]});
	}

	sort(vec.begin(), vec.end());

	for (int i = 0; i < n; i++) {
		int x = lower_bound(vec.begin(), vec.end(), make_pair(A[i], i)) - vec.begin();
		Upd(x, x+1, i);
		Upd(x+1, MXN, -1);
	}
	for (int i = 0; i < q; i++) {
		int x = lower_bound(vec.begin(), vec.end(), make_pair(A[X[i]], X[i])) - vec.begin();
		Upd(x, x+1, -X[i]);
		Upd(x+1, MXN, 1);
		A[X[i]] = V[i];
		x = lower_bound(vec.begin(), vec.end(), make_pair(V[i], X[i])) - vec.begin();
		Upd(x, x+1, X[i]);
		Upd(x+1, MXN, -1);
		X[i] = seg[1];
	}
	return X;
}

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