Submission #206457

#	Time	Username	Problem	Language	Result	Execution time	Memory
206457		GioChkhaidze	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	1783 ms	72060 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"
#define Tree int h,int l,int r
#define Left (h<<1),l,(l+r)>>1
#define Right ((h<<1)|1),((l+r)>>1)+1,r
#define ll long long
#define pb push_back
#define F first
#define S second
using namespace std;
const int N=5e5+5;
int n,q,Xx,Yy,L,R,dl,S,a[N],pos[N],x[N],inf=-1e9;
vector < int > answer;  
vector < pair < pair < int , int > , pair < bool , int >  > > s;
typedef struct { int x; int add; } res;
res v[8*N];

inline void Shift(Tree) {
	if (!v[h].add) return ;
	v[(h<<1)].x+=v[h].add;
	v[((h<<1)|1)].x+=v[h].add;
	v[(h<<1)].add+=v[h].add;
	v[((h<<1)|1)].add+=v[h].add;
	v[h].add=0;
}

void Upd(Tree) {
	if (R<l || r<L) return ;
	if (L<=l && r<=R) { v[h].add+=dl; v[h].x+=dl; return ; }
	Shift(h,l,r);
	Upd(Left),Upd(Right);
	v[h].x=max(v[(h<<1)].x,v[((h<<1)|1)].x);
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	n=A.size(),q=X.size();
	
	for (int i=1; i<=n; i++) {
		a[i]=A[i-1];
		s.pb({{a[i],i},{0,i}});
	}
	
	for (int i=1; i<=q; i++) {
		pos[i]=X[i-1]+1,x[i]=V[i-1];
		s.pb({{x[i],pos[i]},{1,i}});
	}
	
	sort(s.begin(),s.end()),S=s.size();
	
	for (int i=0; i<S; i++) 
		if (!s[i].S.F) 
			a[s[i].S.S]=i+1;
				else 
			x[s[i].S.S]=i+1;
		
	for (int i=1; i<=4*S; i++) 
		v[i].x=inf-1;
		
	for (int i=1; i<=n; i++) {
		L=a[i],R=a[i],dl=-inf+i,Upd(1,1,S);
		L=a[i]+1,R=S,dl=-1,Upd(1,1,S);
	}

	for (int i=1; i<=q; i++) {	
		Xx=a[pos[i]],Yy=x[i];
 		L=Xx,R=Xx,dl=inf-pos[i],Upd(1,1,S);
		L=min(Xx,Yy)+1,R=max(Xx,Yy)-1;
		if (Xx<=Yy) dl=1; else dl=-1;
		if (L<=R) Upd(1,1,S);	
		L=Yy,R=Yy,dl=-inf+pos[i],Upd(1,1,S);
		a[pos[i]]=x[i];
		answer.push_back(v[1].x);
	}

	return answer;
}

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