Submission #404669

#	Time	Username	Problem	Language	Result	Execution time	Memory
404669		Antekb	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	69 ms	6444 KiB

joi2019_ho_t4

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int tab[N][3], tab2[N];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	long long ans=0;
	for(int i=0; i<2*n; i++){
		int x, y;
		cin>>x>>y;
		if(x>n){
			ans+=x-n;
			x=n;
		}
		if(x<1){
			ans+=1-x;
			x=1;
		}
		if(y<1){
			ans+=1-y;
			y=1;
		}
		if(y>2){
			ans+=y-2;
			y=2;
		}
		//cout<<ans<<" "<<x<<" "<<y<<"\n";
		tab[x][y]++;
	}
	/*for(int i=1; i<=n; i++){
		cin>>tab[i][1];
	}
	for(int i=1; i<=n; i++){
		cin>>tab[i][2];
	}*/
	long long ile=0, wsk1=1, wsk2=1;
	for(int i=1; i<=n; i++)tab2[i]=tab[i][1]+tab[i][2];
	for(int i=1; i<=n; i++){
		ile+=tab2[i];
		ans+=abs(ile-2*i);
		while(wsk1<i && tab[i][1]>1){
			if(tab[wsk1][1]==0){
				tab[i][1]--;
				tab[wsk1][1]++;	
			}
			wsk1++;
		}
		while(wsk2<i && tab[i][2]>1){
			if(tab[wsk2][2]==0){
				tab[i][2]--;
				tab[wsk2][2]++;	
			}
			wsk2++;
		}
		
			while(wsk1<=i && tab[i][2]>1){
				if(tab[wsk1][1]==0){
					tab[i][2]--;
					ans++;
					tab[wsk1][1]++;	
				}
				wsk1++;
			}
			while(wsk2<=i && tab[i][1]>1){
				if(tab[wsk2][2]==0){
					tab[i][1]--;
					ans++;
					tab[wsk2][2]++;	
				}
				wsk2++;
			}
			if(tab[i][1]!=0){
				tab[i+1][1]+=tab[i][1]-1;
				tab[i][1]=1;
			}
			if(tab[i][2]!=0){
				tab[i+1][2]+=tab[i][2]-1;
				tab[i][2]=1;
			}
		
		/*for(int j=1; j<=n; j++){
		cout<<tab[j][1]<<" ";
		}
		cout<<"\n";
		for(int j=1; j<=n; j++){
			cout<<tab[j][2]<<" ";
		}
		cout<<"\n";
		cout<<wsk1<<" "<<wsk2<<"\n";*/
	}
	cout<<ans;
}

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