제출 #1027018

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1027018		bane	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	23 ms	6676 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<vector<int>> AllElements;
	for (int i = 0; i < (int)A.size(); i++)AllElements.push_back({A[i], i, 1});
	for (int i = 0; i < (int)V.size(); i++)AllElements.push_back({V[i], i, 2});
	sort(AllElements.begin(), AllElements.end());
	vector<int>AI((int)A.size());
	vector<int>VI((int)V.size());
	for (int i = 0; i < (int)AllElements.size(); i++){
		if (AllElements[i][2] == 2){
			VI[AllElements[i][1]] = i;
		}else{
			AI[AllElements[i][1]] = i;
		}
		if (!i || AllElements[i][0] != AllElements[i - 1][0])compress[AllElements[i][0]] = 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,AI[i], AI[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,AI[X[i]], AI[X[i]], -X[i] - 1);

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

		st.upd(0,n-1,1,compress[A[i]],n - 1, -1);
		st.upd(0,n-1,1,AI[i], AI[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