Submission #547633

#	Time	Username	Problem	Language	Result	Execution time	Memory
547633		cig32	Bubble Sort 2 (JOI18_bubblesort2)	C++17	17 / 100	9086 ms	5800 KiB

bubblesort2

#include "bubblesort2.h"

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
  int N=A.size();
	int Q=X.size();
	std::vector<int> answer(Q);
	for (int j=0;j<Q;j++) {
		A[X[j]] = V[j];
    
    int B[N];
    for(int i=0; i<N; i++) B[i] = A[i];
    std::sort(B, B+N);
    int P[N];
    std::unordered_map<int, std::queue<int> >mp;
    for(int i=0; i<N; i++) mp[B[i]].push(i);
    answer[j] = 0;
    for(int i=0; i<N; i++) {
      P[i] = mp[A[i]].front();
      mp[A[i]].pop();
      answer[j] = std::max(answer[j], i - P[i]);
    }
	}
	return answer;
}

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