제출 #255591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
255591		kshitij_sodani	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2009 ms	62724 KiB

bubblesort2

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second

 
#include "bubblesort2.h"
int ind[1000001];
int tree[4000001];
int lazy[4000001];
int tree2[1000001];
void u(int i,int j){
	while(i<1000001){
		tree2[i]+=j;
		i+=(i&-i);
	}
}
int s(int i){
	int su=0;
	while(i>0){
		su+=tree2[i];
		i-=(i&-i);
	}
	return su;
}
void push(int no,int l,int r){
	tree[no]+=lazy[no];
	if(l<r){
		lazy[no*2+1]+=lazy[no];
		lazy[no*2+2]+=lazy[no];
	}
	lazy[no]=0;

}
void update(int no,int l,int r,int aa,int bb,int val){
	push(no,l,r);
	if(r<aa or l>bb){
		return;
	}
	if(aa<=l and r<=bb){
		tree[no]+=val;
		if(l<r){
			lazy[no*2+1]+=val;
			lazy[no*2+2]+=val;
		}
	}
	else{
		int mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb,val);
		update(no*2+2,mid+1,r,aa,bb,val);
		tree[no]=max(tree[no*2+1],tree[no*2+2]);
	}
}
void update2(int no,int l,int r,int i,int val){
	push(no,l,r);
	if(l==r){
		tree[no]=val;
	}
	else{
		int mid=(l+r)/2;
		push(no*2+1,l,mid);
		push(no*2+2,mid+1,r);
		if(i<=mid){
			update2(no*2+1,l,mid,i,val);
		}
		else{
			update2(no*2+2,mid+1,r,i,val);
		}
		tree[no]=max(tree[no*2+1],tree[no*2+2]);
	}
}

int val[500001];
std::vector<int> countScans(std::vector<int> it,std::vector<int> X,std::vector<int> V){
	int q=X.size();
	int n=it.size();
	vector<pair<pair<int,int>,int>> cur;

	for(int i=0;i<n;i++){
		cur.pb({{it[i],i},i});
	}
	for(int i=0;i<q;i++){
		cur.pb({{V[i],X[i]},i+n});
	}
	sort(cur.begin(),cur.end());
	for(int i=0;i<n+q;i++){
		ind[cur[i].b]=i;
	}
	for(int i=0;i<4*(n+q);i++){
		tree[i]=-1e9;
	}
	vector<int> ans;
	for(int i=0;i<n;i++){
		u(ind[i]+1,1);
	}
	for(int i=0;i<n;i++){
		val[i]=ind[i];
		update2(0,0,n+q-1,ind[i],i-s(ind[i]));
	}
	for(int i=0;i<q;i++){
		u(val[X[i]]+1,-1);
		u(ind[i+n]+1,1);
		update2(0,0,n+q-1,ind[i+n],X[i]-s(ind[i+n]));
		update2(0,0,n+q-1,val[X[i]],-1e9);

		if(ind[i+n]<n+q-1){
			update(0,0,n+q-1,ind[i+n]+1,n+q-1,-1);
		}
		if(val[X[i]]<n+q-1){
			update(0,0,n+q-1,val[X[i]]+1,n+q-1,1);
		}

		val[X[i]]=ind[i+n];
		ans.pb(tree[0]);
	}
	/*for(auto j:ans){
		cout<<j<<",";
	}
	cout<<endl;*/
	return ans;
}
 
//#define endl '\n'
 
/*int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int nn,qq;
	cin>>nn>>qq;
	int pp;
	vector<int> ac;
	vector<int> bc;
	vector<int> dc;
 
	for(int i=0;i<nn;i++){
		cin>>pp;
		ac.pb(pp);
	}
	for(int i=0;i<qq;i++){
		cin>>pp;
		bc.pb(pp);
		cin>>pp;
		dc.pb(pp);
	}
	countScans(ac,bc,dc);
 
	return 0;
}*/

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