Submission #884016

#	Time	Username	Problem	Language	Result	Execution time	Memory
884016		vjudge1	Bubble Sort 2 (JOI18_bubblesort2)	C++17	17 / 100	9038 ms	4444 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 __gnu_pbds;
using namespace std;
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int n;
int a[500005];
int aib[500005];
int calcmax()
{
    ordered_set s;
    int mxm=0;
    for(int i=0;i<n;i++)
    {
        s.insert({a[i],i});
        int cv = s.order_of_key({a[i],i});
        mxm = max(mxm, i-cv);
    }
    return mxm;
}
std::vector<int> countScans(std::vector<int> A, std::vector<int> qp, std::vector<int> qv){
	int q=qp.size();
	n=A.size();
	for(int i=0;i<n;i++)
        a[i]=A[i];
	std::vector<int> answer(q);
	for (int i=0;i<q;i++)
	{
        a[qp[i]] = qv[i];
        answer[i] = calcmax();
	}
	return answer;
}

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