Submission #1026921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026921		bane	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	8 ms	2904 KiB

bubblesort2

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

using namespace std;

map<int,int> compress;
int n = 1;

struct segment_tree{
	int t[1'000'001 * 3], lz[1'000'001 * 3];

	void build(int l = 0, int r = n - 1, int k = 1){
		if (l == r){
			t[k] = 0;
			lz[k] = 0;
			return;
		}
		build(l,(l+r)/2,k*2);
		build((l+r)/2+1,r,k*2+1);
		t[k] = 0;
		lz[k] = 0;
	}

	void push(int k, int l, int r){
		t[k] += lz[k];
		if (l != r){
			lz[k * 2] += lz[k];
			lz[k * 2 + 1] += lz[k];
		}
		lz[k] = 0;
	}

	void upd(int l, int r, int k, int L, int R, int V){
		//cout << l << " " << r << " " << L << " " << R << " " << V << endl;
		push(k,l,r);
		if (l > R || r < L)return;
		if (l >= L && r <= R){
			lz[k] += V;
			push(k,l,r);
			return;
		}
		int mid = (l+r) / 2;
		upd(l,mid,k*2,L,R,V);
		upd(mid+1,r,k*2+1,L,R,V);
		t[k] = max(t[k * 2], t[k * 2 + 1]);
	}

	int get(int W, int l = 0, int r = n - 1, int k = 1){
		push(k,l,r);
		if (l == r){
			return t[k];
		}
		int mid = (l+r)/2;
		if (W <= mid)return get(W,l,mid,k*2);
		else return get(W,mid+1,r,k*2+1);
	}
} st;
vector<int> countScans(vector<int> A, vector<int> X,vector<int> V){
	int Q = X.size();
	vector<int> answer(Q);
	
	vector<int> AllElements;
	for (int i = 0; i < (int)A.size(); i++)AllElements.push_back(A[i]);
	for (int i = 0; i < (int)V.size(); i++)AllElements.push_back(V[i]);
	sort(AllElements.begin(), AllElements.end());
	AllElements.erase(unique(AllElements.begin(), AllElements.end()), AllElements.end());
	for (int i = 0; i < (int)AllElements.size(); i++) compress[AllElements[i]] = i;
	n = (int) AllElements.size();
	st.build();
	for (int i = 0; i < (int)A.size(); i++){
		st.upd(0,n-1,1,compress[A[i]],n - 1, -1);
		st.upd(0,n-1,1,compress[A[i]], compress[A[i]], i + 1);
		//for (int j = 0; j < n; j++)cout << st.get(j) << ' ';
		//cout << endl;
	}

	for (int i = 0; i < (int)X.size(); i++){
		st.upd(0,n-1,1,compress[A[X[i]]], n - 1, 1);
		st.upd(0,n-1,1,compress[A[X[i]]], compress[A[X[i]]], -X[i] - 1);

		A[X[i]] = V[i];

		st.upd(0,n-1,1,compress[A[i]],n - 1, -1);
		st.upd(0,n-1,1,compress[A[i]], compress[A[i]], i + 1);
		st.push(1,0,n-1);
		answer[i] = st.t[1];
	}
	return answer;
}

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