Submission #884072

#	Time	Username	Problem	Language	Result	Execution time	Memory
884072		vjudge1	Bubble Sort 2 (JOI18_bubblesort2)	C++17	38 / 100	9054 ms	5468 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<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int n;
int a[500005];
int init[500005];
/*struct node
{
    int val;
    int lazy;
    int tole;
    int tori;
};
vector<node> aint[2000005];

void propagate_mare(int nod)
{

}
void propagate_mic(int nod, int c)
{

}

void upd_mare_plus(int nod, int st, int dr, int le, int ri, int newv)
{

}
void upd_mic_plus(int nod, int st, int dr, int le, int ri, int newv, int c)
{

}

void upd_mare_egal(int nod, int st, int dr, int le, int ri, int newv)
{

}
void upd_mic_egal(int nod, int st, int dr, int le, int ri, int newv, int c)
{

}*/
pair<int,int> v[500005];
int calcmax()
{
    for(int i=0;i<n;i++)
    {
        v[i] = {a[i],i};
    }
    sort(v,v+n);
    int mxm=0;
    for(int i=0;i<n;i++)
    {
        mxm = max(mxm, v[i].second - i);
    }
    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;
}
/**
4 2
1 2 3 4
0 3
2 1
*/

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