Submission #884095

#	Time	Username	Problem	Language	Result	Execution time	Memory
884095		vjudge1	Bubble Sort 2 (JOI18_bubblesort2)	C++17	60 / 100	3385 ms	12896 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 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;
}
ordered_set s;
set<int> pozs[105];
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);
	if(n<=8000)
    {
        for(int i=0;i<q;i++)
        {
            a[qp[i]] = qv[i];
            answer[i] = calcmax();
        }
    }
    else
    {
        for(int i=0;i<n;i++)
        {
            s.insert({a[i],i});
            pozs[a[i]].insert(i);
        }
        for(int i=0;i<q;i++)
        {
            pozs[a[qp[i]]].erase(qp[i]);
            s.erase({a[qp[i]],qp[i]});
            a[qp[i]] = qv[i];
            s.insert({a[qp[i]],qp[i]});
            pozs[a[qp[i]]].insert(qp[i]);
            int mxm=0;
            for(int j=0;j<=100;j++)
            {
                if(pozs[j].empty())
                    continue;
                auto it = pozs[j].rbegin();
                int x = *it;
                //for(auto x:pozs[j])
                    mxm = max(mxm, x - (int)s.order_of_key({a[x],x}));
            }
            answer[i] = mxm;
        }
    }
	return answer;
}
/**
4 2
1 2 3 4
0 3
2 1
*/

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