Submission #887115

#	Time	Username	Problem	Language	Result	Execution time	Memory
887115		amirhoseinfar1385	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	1691 ms	38952 KiB

bubblesort2

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;

int n,q;
int kaf=(1<<20);
struct segment{
	struct node{
		int maxa,lazy;
		node(){
			maxa=lazy=0;
		}
	};
	node seg[(1<<21)];
	void calc(int i){
		if(i>=kaf){
			seg[i].maxa+=seg[i].lazy;
			seg[i].lazy=0;
			return ;
		}
		seg[i].maxa=max(seg[(i<<1)].maxa+seg[(i<<1)].lazy,seg[(i<<1)^1].maxa+seg[(i<<1)^1].lazy);
	}
	void shift(int i){
		if(i>=kaf){
			calc(i);
			return ;
		}
		seg[(i<<1)].lazy+=seg[i].lazy;
		seg[(i<<1)^1].lazy+=seg[i].lazy;
		seg[i].lazy=0;
		return ;
	}
	void upd(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].lazy+=w;
			shift(i);
			calc(i);
			return ;
		}
		int m=(l+r)>>1;
		shift(i);
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
		calc(i);
	}
}seg;


std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	n=A.size(),q=X.size();
	vector<pair<int,int>>allind;
	for(int i=0;i<n;i++){
		allind.push_back(make_pair(A[i],i));
	}
	for(int i=0;i<q;i++){
		allind.push_back(make_pair(V[i],X[i]));
	}
	sort(allind.begin(),allind.end());
	allind.resize(unique(allind.begin(),allind.end())-allind.begin());
	int sz=allind.size();
	for(int i=0;i<n;i++){
		int p=lower_bound(allind.begin(),allind.end(),make_pair(A[i],i))-allind.begin();
		seg.upd(1,0,kaf-1,p,p,i);
		seg.upd(1,0,kaf-1,p+1,sz,-1);
	}
	vector<int>res(q);
	for(int i=0;i<q;i++){
		int ind=X[i],val=V[i],p=lower_bound(allind.begin(),allind.end(),make_pair(A[ind],ind))-allind.begin();
		seg.upd(1,0,kaf-1,p,p,-ind);
		seg.upd(1,0,kaf-1,p+1,sz,1);
		A[ind]=val;
		p=lower_bound(allind.begin(),allind.end(),make_pair(val,ind))-allind.begin();
		seg.upd(1,0,kaf-1,p,p,ind);
		seg.upd(1,0,kaf-1,p+1,sz,-1);
		res[i]=seg.seg[1].maxa>0?seg.seg[1].maxa:0;
	}
	return res;
}

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