Submission #64615

#	Time	Username	Problem	Language	Result	Execution time	Memory
64615		zscoder	Bubble Sort 2 (JOI18_bubblesort2)	C++17	17 / 100	9025 ms	3672 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int solve(vi &v)
{
	pbds t;
	int n=v.size(); int ans=0;
	vector<int> mn(n,int(1e9));
	for(int i=n-1;i>=0;i--)
	{
		mn[i] = v[i];
		if(i+1<n) mn[i]=min(mn[i],mn[i+1]);
	}
	for(int i=0;i<n-1;i++)
	{
		t.insert(mp(v[i],i));
		int cnt = int(t.size()) - t.order_of_key(mp(mn[i+1], -1));
		ans=max(ans,cnt);
	}
	return ans;
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V)
{
	int Q=X.size();
	std::vector<int> answer(Q);
	int n = A.size();
	for(int j=0;j<Q;j++) 
	{
		A[X[j]] = V[j];
		answer[j] = solve(A);
	}
	return answer;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:43:6: warning: unused variable 'n' [-Wunused-variable]
  int n = A.size();
      ^

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