Submission #408773

#	Time	Username	Problem	Language	Result	Execution time	Memory
408773		AmineWeslati	Bubble Sort 2 (JOI18_bubblesort2)	C++14	17 / 100	9099 ms	4284 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;

typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(v) (int)v.size()
#define all(x) begin(x),end(x)

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)

//--------------------------------------------//

int N,Q;
vi a,aa; 

const int MX=5e5+10;

void ckmax(int &x, int y){x=max(x,y);}


vi t(MX,0);
void upd(int idx){
	int i=idx; 
	for(;i<=N; i+=i&-i){
		t[i]++;
	}
}

int get(int idx){
	int i=idx; 
	int ans=0;
	for(;i;i-=i&-i) ans+=t[i];
	return ans;
}

vi countScans(vi A,vi X,vi V){
	N=sz(A); Q=sz(X);
	a.assign(all(A));
	aa.assign(all(A));

	vi ans(Q);
	FOR(idx,0,Q){
		aa[X[idx]]=V[idx];

		vi temp;
		temp.assign(all(aa));
		sort(all(temp));

		int cnt=0;
		unordered_map<int,int>mp;
		for(int x: temp) if(!mp.count(x)) mp[x]=++cnt;
		vi a(N);
		FOR(i,0,N) a[i]=mp[aa[i]];

		vi st,vec(N);
		ROF(i,0,N){
			while(sz(st) && st.back()<a[i]) st.pop_back();

			if(!sz(st)){
				vec[i]=(i!=N-1);
			} 
			else{
				if(st.back()==i+1 && !vec[st.back()])
					vec[i]=0;
				else vec[i]=vec[st.back()]+1;
			}

			st.pb(i);
		}
		
		t.assign(N+10,0);
		FOR(i,0,N){
			ckmax(vec[i],i-get(a[i]));
			upd(a[i]);
		}

		ans[idx]=0;
		FOR(i,0,N) ckmax(ans[idx],vec[i]);

	}
	return ans; 
}

/*

4 2
1 2 3 4
0 3
2 1

*/

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