Submission #1123436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123436		emptypringlescan	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	54 ms	9148 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    pair<long long,long long> arr[2*n];
    long long ans=0;
    int got[n+1][2];
    memset(got,0,sizeof(got));
    for(int i=0; i<2*n; i++){
		cin >> arr[i].first >> arr[i].second;
		if(arr[i].first<1){
			ans+=1-arr[i].first;
			arr[i].first=1;
		}
		if(arr[i].first>n){
			ans+=arr[i].first-n;
			arr[i].first=n;
		}
		if(arr[i].second<1){
			ans+=1-arr[i].second;
			arr[i].second=1;
		}
		if(arr[i].second>2){
			ans+=arr[i].second-2;
			arr[i].second=2;
		}
		got[arr[i].first][arr[i].second-1]++;
	}
	vector<pair<int,int> > st[2];
	for(int i=1; i<=n; i++){
		for(int j=0; j<2; j++){
			if(got[i][j]<1){
				if(st[j].empty()||st[j].back().first==0){
					st[j].push_back({0,i});
				}
				else{
					ans+=i-st[j].back().second;
					st[j].pop_back();
				}
				got[i][j]=1;
			}
			else{
				while(got[i][j]>1){
					if(st[j].empty()||st[j].back().first==1){
						st[j].push_back({1,i});
					}
					else{
						ans+=i-st[j].back().second;
						st[j].pop_back();
					}
					got[i][j]--;
				}
			}
		}
		while(!st[0].empty()&&!st[1].empty()&&st[0].back().first!=st[1].back().first){
			ans+=1+abs(st[0].back().second-st[1].back().second);
			st[0].pop_back();
			st[1].pop_back();
		}
	}
	assert(st[0].empty()&&st[1].empty());
	cout << ans;
}

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