Submission #547622

#	Time	Username	Problem	Language	Result	Execution time	Memory
547622		cig32	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	2694 ms	736 KiB

bubblesort2

#include "bubblesort2.h"

#include <cstdio>
#include <cstdlib>
#include <vector>



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 bucket[N+1];
    for(int i=0; i<=N; i++) bucket[i] = 2e9;
    int ma = 1;
    bucket[1] = A[N-1];
    for(int k=N-2;k>=0; k--) {
      auto it = std::lower_bound(bucket + 1, bucket + N + 1, A[k]);
      int d = std::distance(bucket, it);
      bucket[d] = std::min(bucket[d], A[k]);
      ma = std::max(ma, d);
    }
    answer[j] = ma - 1;
	}
	return answer;
}

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