Submission #1158129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158129		8pete8	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	1379 ms	103196 KiB

bubblesort2

#include "bubblesort2.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<complex>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
//#define int long long
//#define double long double
using namespace std;
using cd = complex<double>;
double const PI=acos(-1);
const int mod=1e9+7,mxn=1e6+5,inf=1e9,minf=-1e9,lg=27,Mxn=lg*mxn;
int n,mx;
struct seg{
	int inv[4*mxn+10],lazy[4*mxn+10];
	void apply(int pos,int x){
		lazy[pos]+=x;
		inv[pos]+=x;
	}
	void push(int pos,int l,int r){
		if(l!=r){
			apply(pos*2,lazy[pos]);
			apply(pos*2+1,lazy[pos]);
		}
		lazy[pos]=0;
	}
	void pull(int pos){
		inv[pos]=max(inv[pos*2],inv[pos*2+1]);
	}
	void updaterange(int ql,int qr,int x,int pos=1,int l=0,int r=n){
		//update inversion
		if(l>qr||r<ql)return;
		if(ql<=l&&r<=qr)return void(apply(pos,x));
		int mid=l+(r-l)/2;
		push(pos,l,r);
		updaterange(ql,qr,x,pos*2,l,mid);
		updaterange(ql,qr,x,pos*2+1,mid+1,r);
		pull(pos);
	}
	int qry2(int ql,int qr,int pos=1,int l=0,int r=n){
		if(l>qr||r<ql)return minf;
		if(ql<=l&&r<=qr)return inv[pos];
		int mid=l+(r-l)/2;
		push(pos,l,r);
		return max(qry2(ql,qr,pos*2,l,mid),qry2(ql,qr,pos*2+1,mid+1,r));
	}
}t;
int val[mxn+10],last[mxn+10];
priority_queue<int>pos[mxn+10];
void upd(int x,int v){
	while(!pos[val[x]].empty()&&val[pos[val[x]].top()]!=val[x])pos[val[x]].pop();
	if(v==1){
		pos[val[x]].push(x);
		if(pos[val[x]].top()==x){
			t.updaterange(val[x],val[x],(x+1-last[val[x]])*v);
			last[val[x]]=x+1;
		}
	}
	else{
		if(pos[val[x]].top()==x){
			pos[val[x]].pop();
			while(!pos[val[x]].empty()&&((val[pos[val[x]].top()]!=val[x])||(pos[val[x]].top()==x)))pos[val[x]].pop();
			if(pos[val[x]].empty())last[val[x]]=0;
			else last[val[x]]=pos[val[x]].top()+1;
			t.updaterange(val[x],val[x],(x+1-last[val[x]])*v);
		}
	}
	t.updaterange(val[x],n,-v);
}
vector<int>comp;
vector<int32_t> countScans(vector<int32_t> A,vector<int32_t> X,vector<int32_t> V){
	vector<int>ans;
	for(auto i:A)comp.pb(i);
	for(auto i:V)comp.pb(i);
	sort(all(comp));
	comp.erase(unique(all(comp)),comp.end());
	for(auto &i:A)i=lb(all(comp),i)-comp.begin()+1;
	for(auto &i:V)i=lb(all(comp),i)-comp.begin()+1;
	n=comp.size();
	for(int i=0;i<A.size();i++){
		val[i]=A[i];
		upd(i,1);
	}
	for(int i=0;i<X.size();i++){
		upd(X[i],-1);
		val[X[i]]=V[i];
		upd(X[i],1);
		ans.pb(t.inv[1]);
	}
	return ans;
}

/*
if we see each pass as a movement of prefix max moving through number that is less
and stop only at the end or find a new prefix max

we can observe that there can only be atmost 1 number moving through each position
meaning if position i has inversion cnt = x it will take atleast x passes to move every greater element infront behind

so the answer should be max(inversion cnt for each pos)?

if we look at the min element in the array the only posible candidate to be max inversion
has to be on the right side
so the total candidate for the answer is just the suffix min of the array

due to monotonicity can we create segtree on value?
so when update val we add 1 everything from [1,val-1]
no? case like 2 4 1 5
when update 4 value 2 will also be added and become a possible answer when updated to 2 4 5 5

we update with -1 instead? to not interfere with the max ans
considering inversion = i - cnt of number less vi that is infront
when update val we add -1 to [val,mx]
now the pos that is not on suffix min will have less value than the actual inversion
which is greate because now it wont interfere with the correct ans
*/

Compilation message (stderr)

bubblesort2.cpp:34:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   34 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
bubblesort2.cpp:44:33: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   44 |         void apply(int pos,int x){
      |                                 ^
bubblesort2.cpp:48:38: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   48 |         void push(int pos,int l,int r){
      |                                      ^
bubblesort2.cpp:55:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   55 |         void pull(int pos){
      |                          ^
bubblesort2.cpp:58:71: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   58 |         void updaterange(int ql,int qr,int x,int pos=1,int l=0,int r=n){
      |                                                                       ^
bubblesort2.cpp:68:57: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   68 |         int qry2(int ql,int qr,int pos=1,int l=0,int r=n){
      |                                                         ^
bubblesort2.cpp:78:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   78 | void upd(int x,int v){
      |                     ^
bubblesort2.cpp:99:81: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   99 | vector<int32_t> countScans(vector<int32_t> A,vector<int32_t> X,vector<int32_t> V){
      |                                                                                 ^

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