Submission #1160597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160597		Newtonabc	Bubble Sort 2 (JOI18_bubblesort2)	C++20	38 / 100	25 ms	25412 KiB

bubblesort2

#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1<<21;
struct stree{
	vector<int> lz,s,arr;
	int sz;
	void init(int n){
		lz.resize(n,0);
		s.resize(n,0);
		arr.resize(n,0);
	}
	void pushlz(int l,int r,int idx){
		if(!lz[idx]) return;
		s[idx]+=lz[idx];
		if(l!=r) lz[idx*2]+=lz[idx],lz[idx*2+1]+=lz[idx];
		lz[idx]=0;
	}
	void build(int l,int r,int idx){
		if(l==r){
			s[idx]=arr[l];
			return;
		}
		int m=(l+r)/2;
		build(l,m,idx*2);
		build(m+1,r,idx*2+1);
		s[idx]=max(s[idx*2],s[idx*2+1]);
	}
	void update(int l,int r,int idx,int a,int b,int val){
		pushlz(l,r,idx);
		if(b<l || a>r) return;
		if(a<=l && b>=r){
			lz[idx]=val;
			pushlz(l,r,idx);
			return;
		}
		int m=(l+r)/2;
		update(l,m,idx*2,a,b,val);
		update(m+1,r,idx*2+1,a,b,val);
		s[idx]=max(s[idx*2],s[idx*2+1]);
	}
	int query(int l,int r,int idx,int a,int b){
		pushlz(l,r,idx);
		if(a>r || b<l) return INT_MIN;
		if(a<=l && b>=r) return s[idx];
		int m=(l+r)/2;
		return max(query(l,m,idx*2,a,b),query(m+1,r,idx*2+1,a,b));
	}
};
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	int q=X.size();
	int n=A.size();
	std::vector<int> answer(q);
	stree s;
	s.init(N);
	vector<int> v;
	for(auto tmp:A) v.push_back(tmp);
	for(auto tmp:V) v.push_back(tmp);
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	int m=v.size();
	for(auto &tmp:A){
		tmp=lower_bound(v.begin(),v.end(),tmp)-v.begin();
		//cout<<tmp <<" ";
	}
	//cout<<"\n";
	for(auto &tmp:V){
		tmp=lower_bound(v.begin(),v.end(),tmp)-v.begin();
	}
	for(int i=0;i<n;i++){
		s.update(0,m-1,1,A[i],A[i],i);
		s.update(0,m-1,1,A[i]+1,m-1,-1);
	}
	//for(int i=0;i<m;i++) cout<<s.query(0,m-1,1,i,i) <<" ";
	cout<<"\n";
	for(int i=0;i<q;i++){
		//change A[X[i]] to V[i]
		s.update(0,m-1,1,A[X[i]],A[X[i]],-X[i]);
		s.update(0,m-1,1,A[X[i]]+1,m-1,1);
		A[X[i]]=V[i];
		s.update(0,m-1,1,A[X[i]],A[X[i]],X[i]);
		s.update(0,m-1,1,A[X[i]]+1,m-1,-1);
		answer[i]=s.query(0,m-1,1,0,m-1);
	}

	return answer;
}

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