Submission #850800

#	Time	Username	Problem	Language	Result	Execution time	Memory
850800		vjudge1	Bubble Sort 2 (JOI18_bubblesort2)	C++17	17 / 100	9058 ms	2304 KiB

bubblesort2

#include <bits/stdc++.h>
#define all(v) ((v).begin(),(v).end())
#define ll long long
#define F first
#define S second
const ll mod = 1e9 + 7;
const ll mxN = 1e5 + 2;
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using indexed_set = tree<T,null_type,less<T>,rb_tree_tag, tree_order_statistics_node_update>;

// int readInt(){
// 	int i;
// 	if(scanf("%d",&i)!=1){
// 		fprintf(stderr,"Error while reading input\n");
// 		exit(1);
// 	}
// 	return i;
// }

vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	int Q=X.size();
	int N = A.size();
	set<pair<int,int>>s;
	vector<int>ans;
	for(int i = 0; i < Q;i++){
		A[X[i]] = V[i];
		s.clear();
		int x = 0;
		indexed_set<int>S;
		for(int j = 0;j < N;j++){
			int x = 0;
			if(S.upper_bound(A[j]) != S.end()) x = S.size() - S.order_of_key(*(S.upper_bound(A[j])));
			s.insert({x,j});
			S.insert(A[j]);
		}
		auto y = s.end();
		y--;
		ans.push_back((*y).first);
	}
	return ans;
}
// int main(){
// 	int N,Q;
// 	N=readInt();
// 	Q=readInt();
// 
// 	std::vector<int> A(N);
// 	for(int i=0;i<N;i++)
// 		A[i]=readInt();
// 
// 	std::vector<int> X(Q),V(Q);
// 	for(int j=0;j<Q;j++){
// 		X[j]=readInt();
// 		V[j]=readInt();
// 	}
// 
// 	std::vector<int> res=countScans(A,X,V);
// 
// 	for(int j=0;j<int(res.size());j++)
// 		printf("%d\n",res[j]);
// }

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:32:7: warning: unused variable 'x' [-Wunused-variable]
   32 |   int x = 0;
      |       ^

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