Submission #70798

#	Time	Username	Problem	Language	Result	Execution time	Memory
70798		dnass	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	9060 ms	1312 KiB

bubblesort2

#include "bubblesort2.h"
#include <set>
#include <map>
#include <algorithm>
#include <iterator>
#include <cstdio>
#include <cmath>
using namespace std;

int n, q;

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
	vector<int> ans;
	n = A.size();
	q = X.size();
	for(int i=0;i<q;i++){
		A[X[i]] = V[i];
		vector<int> srt;
		for(int j=0;j<n;j++) srt.push_back(A[j]);
		sort(srt.begin(), srt.end());
		map<int, int> seen_before;
		for(int j=0;j<n;j++) seen_before[A[j]] = 0;
		int mx = -1;
		for(int j=0;j<n;j++){
			vector<int>::iterator it;
			it = lower_bound(srt.begin(), srt.end(), A[j]);
			int x = it-srt.begin();
			mx = max(mx, ((int) round(fabs(x+seen_before[A[j]]-j))));
			seen_before[A[j]]++;
		}
		ans.push_back(mx);
	}
	return ans;
}

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