Submission #369847

#	Time	Username	Problem	Language	Result	Execution time	Memory
369847		pure_mem	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	3392 ms	41436 KiB

bubblesort2

#include "bubblesort2.h"
#include <vector>
#include <algorithm>
#include <iostream>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 1e6 + 12;

int n, q, m, t[N * 4], tt[N * 4];
vector< pair<int, int> > ord;

void push(int v){
	if(!tt[v])
		return;
	t[v * 2] += tt[v], t[v * 2 + 1] += tt[v];
	tt[v * 2] += tt[v], tt[v * 2 + 1] += tt[v];
	tt[v] = 0;
}

void upd(int v, int tl, int tr, int l, int r, int val){
	if(tl > r || l > tr)
		return;
	if(tl >= l && tr <= r){
		t[v] += val, tt[v] += val;
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	upd(v * 2, tl, tm, l, r, val);
	upd(v * 2 + 1, tm + 1, tr, l, r, val);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}

int get_pos(pair<int, int> x){
	return lower_bound(ord.begin(), ord.end(), x) - ord.begin() + 1;
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
	n = A.size(), q = X.size();
	for(int i = 0;i < n;i++)
		ord.push_back(MP(A[i], i));
	for(int i = 0;i < q;i++)
		ord.push_back(MP(V[i], X[i]));
	sort(ord.begin(), ord.end());
	ord.erase(unique(ord.begin(), ord.end()), ord.end());
	m = (int)ord.size();
	for(int i = 0;i < n;i++){
		int pos1 = get_pos(MP(A[i], i));
		upd(1, 1, m, pos1, pos1, i + 1);
		int pos2 = get_pos(MP(A[i], -1));
		upd(1, 1, m, pos2, m, -1);		
	}
	vector<int> answer(q);
	for(int i = 0;i < q;i++){
		int pos1 = get_pos(MP(A[X[i]], X[i]));
		upd(1, 1, m, pos1, pos1, -X[i] - 1);
		int pos2 = get_pos(MP(A[X[i]], -1));
		upd(1, 1, m, pos2, m, 1);
		A[X[i]] = V[i];		
		pos1 = get_pos(MP(A[X[i]], X[i]));
		upd(1, 1, m, pos1, pos1, X[i] + 1);
		pos2 = get_pos(MP(A[X[i]], -1));
		upd(1, 1, m, pos2, m, -1);
		answer[i] = t[1];
	}
	return answer;
}

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