Submission #1277594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277594		PieArmy	Coin Collecting (JOI19_ho_t4)	C++20	0 / 100	1 ms	576 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;
#define mid ((left+right)>>1)
struct Seg{
	int n,k;
	vector<int>sum,pre,loc;
	void build(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			pre[node]=sum[node]=k;
			loc[node]=left;
			return;
		}
		build(node*2,left,mid);
		build(node*2+1,mid+1,right);
		sum[node]=sum[node*2]+sum[node*2+1];
		if(pre[node*2]>=0||pre[node*2]>pre[node*2+1]+sum[node*2]){
			loc[node]=loc[node*2];
			pre[node]=pre[node*2];
		}
		else{
			loc[node]=loc[node*2+1];
			pre[node]=pre[node*2+1]+sum[node*2];
		}
	}
	void init(int N,int K){
		n=N;
		k=K;
		sum.resize(n<<2);
		pre.resize(n<<2);
		loc.resize(n<<2);
		build();
	}
	int l,r;
	void up(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			sum[node]+=r;
			pre[node]=sum[node];
			return;
		}
		if(l>mid)up(node*2+1,mid+1,right);
		else up(node*2,left,mid);
		sum[node]=sum[node*2]+sum[node*2+1];
		if(pre[node*2]>=0||pre[node*2]>pre[node*2+1]+sum[node*2]){
			loc[node]=loc[node*2];
			pre[node]=pre[node*2];
		}
		else{
			loc[node]=loc[node*2+1];
			pre[node]=pre[node*2+1]+sum[node*2];
		}
	}
	void update(int tar,int val){
		l=tar;r=val;
		up();
	}
	pair<int,pair<int,int>> qu(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left>=l&&right<=r)return pair<int,pair<int,int>>{loc[node],{sum[node],pre[node]}};
		if(left>r||right<l)return pair<int,pair<int,int>>{-1,{0,-1e9}};
		pair<int,pair<int,int>>res,res1=qu(node*2,left,mid),res2=qu(node*2+1,mid+1,right);
		res.sc.fr=res1.sc.fr+res2.sc.fr;
		if(res1.sc.sc>=0||res1.sc.sc>res2.sc.sc+res1.sc.fr){
			res.fr=res1.fr;
			res.sc.sc=res1.sc.sc;
		}
		else{
			res.fr=res2.fr;
			res.sc.sc=res2.sc.sc+res1.sc.fr;
		}
		return res;
	}
	pair<int,pair<int,int>> query(int left,int right){
		l=left;r=right;
		return qu();
	}
};

int n;
int arr[100023][2];
ll ans=0;
Seg seg,seg2;

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){
		seg2.update(tar,x);
		seg2.update(from,-x);
	}
	seg.update(tar,x);
	seg.update(from,-x);
}

void f(int left,int right){
	if(left==right){
		if(arr[left][0]!=1)ans++;
		return;
	}
	pair<int,pair<int,int>> k=seg.query(left,right);
	int mi=k.fr;
	//cout<<left<<" "<<mi<<" "<<right<<endl;
	if(mi==right){
		int a=arr[mi][0],b=arr[mi][1];
		ekle(mi,mi-1,0,max(0,arr[mi][0]-1-!b));
		ekle(mi,mi-1,1,max(0,arr[mi][1]-1-!a));
		f(mi,mi);
		f(left,mi-1);
		/*for(int j=0;j<2;j++){
			for(int i=0;i<n;i++){
				cout<<arr[i][j]<<" ";
			}
			cout<<endl;
		}
		cout<<endl;*/
		return;
	}
	int s=k.sc.fr+2*(right-left+1),a=k.sc.sc+2*(mi-left+1),b=s-a;
	int ust=seg2.query(left,mi).sc.fr,alt=a-ust;
	int need=(a-(mi-left+1)*2);
	if(need<=abs(ust-alt)){
		if(ust>alt){
			ekle(mi,mi+1,0,need);
		}
		else{
			ekle(mi,mi+1,1,need);
		}
	}
	else{
		if(ust>alt){
			ekle(mi,mi+1,0,ust-alt);
			need-=ust-alt;
			ust=alt;
		}
		else{
			ekle(mi,mi+1,1,alt-ust);
			need-=alt-ust;
			alt=ust;
		}
		ekle(mi,mi+1,0,need/2);
		ekle(mi,mi+1,1,(need+1)/2);
	}
	/*for(int j=0;j<2;j++){
		for(int i=0;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;
	seg.init(n,-2);
	seg2.init(n,0);
	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-1][p.sc-1]++;
		seg.update(p.fr-1,1);
		if(p.sc-1==0){
			seg2.update(p.fr-1,1);
		}
	}
	/*cout<<ans<<endl;
	for(int j=0;j<2;j++){
		for(int i=0;i<n;i++){
			cout<<arr[i][j]<<" ";
		}
		cout<<endl;
	}*/
	f(0,n-1);
	cout<<ans<<endl;
}

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