제출 #1141079

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141079		Noproblem29	Bubble Sort 2 (JOI18_bubblesort2)	C++20	0 / 100	24 ms	1728 KiB

bubblesort2

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

const int N=1e6+100;
pair<int,int> t[N*4];
int add[N*4];
pair<int,int> operator +(const pair<int,int>&x,const pair<int,int>&y){
	pair<int,int>res;
	res.first=x.first+y.first;
	res.second=max(x.second,y.second);
	return res;
}
void build(int v,int tl,int tr){
	if(tl==tr){
		t[v]={0,0};
		return;
	}
	int mid=(tl+tr)>>1ll;
	build(v*2,tl,mid);
	build(v*2+1,mid+1,tr);
	t[v]=t[v*2]+t[v*2+1];
}
void push(int v,int tl,int tr){
	if(tl!=tr){
		add[v*2]+=add[v];
		add[v*2+1]+=add[v];
	}
	t[v].second+=add[v];
	add[v]=0;
}
void upd(int v,int tl,int tr,int l,pair<int,int>x){
	push(v,tl,tr);
	if(tl==tr){
		t[v]=x;
		return;
	}
	int mid=(tl+tr)>>1ll;
	if(l<=mid){
		upd(v*2,tl,mid,l,x);
		push(v*2+1,mid+1,tr);
	}
	else{
		upd(v*2+1,mid+1,tr,l,x);
		push(v*2,tl,mid);
	}
	t[v]=t[v*2]+t[v*2+1];
}
void upd(int v,int tl,int tr,int l,int r,int x){
	push(v,tl,tr);
	if(tl>r||tr<l)return;
	if(l<=tl&&tr<=r){
		add[v]+=x;
		push(v,tl,tr);
		return;
	}
	int mid=(tl+tr)>>1ll;
	upd(v*2,tl,mid,l,r,x);
	upd(v*2+1,mid+1,tr,l,r,x);
	t[v]=t[v*2]+t[v*2+1];
}
pair<int,int> get(int v,int tl,int tr,int l,int r){
	push(v,tl,tr);
	if(tl>r||tr<l)return {0,0};
	if(l<=tl&&tr<=r)return t[v];
	int mid=(tl+tr)>>1ll;
	return get(v*2,tl,mid,l,r)+get(v*2+1,mid+1,tr,l,r);
}
vector<pair<int,int>>uni;
vector<int> countScans(vector<int> a,vector<int> x,vector<int> v){
	int q=x.size();
	int n=a.size();
	for(int i=0;i<n;i++){
		uni.push_back({a[i],i});
	}
	for(int i=0;i<q;i++){
		uni.push_back({v[i],x[i]});
	}
	sort(uni.begin(),uni.end());
	uni.resize(unique(uni.begin(),uni.end())-uni.begin());
	vector<int>ans(q);
	build(1,0,uni.size()-1);
	// cout<<uni.size()<<'\n';
	for(int i=0;i<n;i++){
		int pos=lower_bound(uni.begin(),uni.end(),make_pair(a[i],i))-uni.begin();
		auto cur=get(1,0,uni.size()-1,0,pos-1);
		upd(1,0,uni.size()-1,pos,{1,i-cur.first});	
		upd(1,0,uni.size()-1,pos+1,uni.size()-1,-1);
	}
	// cout<<t[1].second<<'\n';
	for(int j=0;j<q;j++){
		int pos=lower_bound(uni.begin(),uni.end(),make_pair(a[x[j]],x[j]))-uni.begin();
		upd(1,0,uni.size()-1,pos,{0,1e9});
		upd(1,0,uni.size()-1,pos+1,uni.size()-1,1);
		a[x[j]]=v[j];
		pos=lower_bound(uni.begin(),uni.end(),make_pair(a[x[j]],x[j]))-uni.begin();
		auto cur=get(1,0,uni.size()-1,0,pos-1);
		upd(1,0,uni.size()-1,pos,{1,x[j]-cur.first});	
		upd(1,0,uni.size()-1,pos+1,uni.size()-1,-1);
		ans[j]=t[1].second;
	}
	return ans;
}

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