Submission #1277708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277708		PieArmy	Coin Collecting (JOI19_ho_t4)	C++20	0 / 100	1 ms	580 KiB

joi2019_ho_t4

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;

struct Fen{
	int n;
	vector<int>tree;
	void init(int N){
		n=N;
		tree.resize(n+1,0);
	}
	void update(int tar,int x){
		while(tar<=n){
			tree[tar]+=x;
			tar+=(tar&-tar);
		}
	}
	int qu(int tar){
		int res=0;
		while(tar>0){
			res+=tree[tar];
			tar-=(tar&-tar);
		}
		return res;
	}
	int query(int left,int right){
		if(left>right)return 0;
		return qu(right)-qu(left-1);
	}
};

int n;
int arr[100023][2];
ll ans=0;
set<int>st;
Fen fen,fen2;

void ekle(int from,int tar,int k,int x){
	if(x==0)return;
	arr[tar][k]+=x;
	arr[from][k]-=x;
	ans+=x;
	if(k==0){
		fen2.update(tar,x);
		fen2.update(from,-x);
	}
	fen.update(tar,x);
	fen.update(from,-x);
}

void f(int left,int right){
	if(left==right){
		if(arr[left][0]!=1)ans++;
		return;
	}
	int mi=-1;
	if(arr[left][0]+arr[left][1]>=2)mi=left;
	else{
		int x=left;
		while(true){
			x=*st.upper_bound(x);
			if(x>right)break;
			if(fen.query(left,x)<2*(x-left+1)){
				st.erase(x);
				continue;
			}
			mi=x;
			break;
		}
	}
	//cout<<left<<" "<<mi<<" "<<right<<endl;
	if(mi==-1||mi==right){
		mi=right;
		int a=arr[mi][0],b=arr[mi][1];
		assert(a+b>=2);
		ekle(mi,mi-1,0,max(0,a-1-!b));
		ekle(mi,mi-1,1,max(0,b-1-!a));
		/*for(int j=0;j<2;j++){
			for(int i=1;i<=n;i++){
				cout<<arr[i][j]<<" ";
			}
			cout<<endl;
		}
		cout<<endl;*/
		f(mi,mi);
		f(left,mi-1);
		return;
	}
	int s=fen.query(left,right),a=fen.query(left,mi),b=s-a;
	int ust=fen2.query(left,mi),alt=a-ust;
	int need=a-2*(mi-left+1);
	assert(need>=0);
	//cout<<need<<endl;
	if(need<=min(arr[mi][0],ust-alt)){
		ekle(mi,mi+1,0,need);
	}
	else if(need<=min(arr[mi][1],alt-ust)){
		ekle(mi,mi+1,1,need);
	}
	else{
		if(ust>alt){
			int x=min(arr[mi][0],ust-alt);
			ekle(mi,mi+1,0,x);
			a-=x;
			b+=x;
			need-=x;
			ust-=x;
		}
		else{
			int x=min(arr[mi][1],alt-ust);
			ekle(mi,mi+1,1,x);
			a-=x;
			b+=x;
			need-=x;
			alt-=x;
		}
		int x=min(min(arr[mi][0],arr[mi][1]),need/2);
		ekle(mi,mi+1,0,x);
		ekle(mi,mi+1,1,x);
		need-=x*2;
		if(need){
			if(arr[mi][0]&&arr[mi][1]){
				int ust2=fen2.query(mi+1,right),alt2=b-ust2;
				if(ust2>alt2){
					ekle(mi,mi+1,1,1);
				}
				else ekle(mi,mi+1,0,1);
			}
			else if(arr[mi][0]){
				ekle(mi,mi+1,0,need);
			}
			else{
				ekle(mi,mi+1,1,need);
			}
		}
	}
	/*for(int j=0;j<2;j++){
		for(int i=1;i<=n;i++){
			cout<<arr[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;*/
	f(left,mi);
	f(mi+1,right);
}

int main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n;
	fen.init(n);
	fen2.init(n);
	for(int i=1;i<=2*n;i++){
		pair<int,int>p;cin>>p.fr>>p.sc;
		if(p.fr<1){
			ans+=1-p.fr;
			p.fr=1;
		}
		if(p.fr>n){
			ans+=p.fr-n;
			p.fr=n;
		}
		if(p.sc<1){
			ans+=1-p.sc;
			p.sc=1;
		}
		if(p.sc>2){
			ans+=p.sc-2;
			p.sc=2;
		}
		arr[p.fr][p.sc-1]++;
		fen.update(p.fr,1);
		if(p.sc-1==0){
			fen2.update(p.fr,1);
		}
	}
	int sum=0;
	st.insert(n+1);
	for(int i=1;i<=n;i++){
		sum+=arr[i][0]+arr[i][1];
		if(sum>=2*i)st.insert(i);
	}
	/*cout<<ans<<endl;
	for(int j=0;j<2;j++){
		for(int i=1;i<=n;i++){
			cout<<arr[i][j]<<" ";
		}
		cout<<endl;
	}*/
	f(1,n);
	cout<<ans<<endl;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63