Submission #203814

#	Time	Username	Problem	Language	Result	Execution time	Memory
203814		kig9981	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	5 ms	376 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;

vector<pair<int,int>> P;
multiset<int> S[2];
int X[100000][2];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N;
	long long ans=0;
	cin>>N;
	P.resize(2*N);
	for(auto &[x,y]: P) cin>>x>>y;
	sort(P.begin(),P.end());
	for(int i=0;i<N;i++) {
		ans+=abs(i+1LL-P[2*i].first)+abs(i+1LL-P[2*i+1].first)+abs(1LL-P[2*i].second)+abs(2LL-P[2*i+1].second);
		if(P[2*i].second>1) {
			auto it=S[0].lower_bound(min(i+1,P[2*i].first));
			if(it!=S[0].end() && (i+1LL-*it)*(i+1LL-P[2*i].first)>=0) {
				ans-=2;
				S[0].erase(it);
				continue;
			}
			S[1].insert(max(i+1,P[2*i].first));
		}
		if(P[2*i+1].second<2) {
			auto it=S[1].lower_bound(min(i+1,P[2*i+1].first));
			if(it!=S[1].end() && (i+1LL-*it)*(i+1LL-P[2*i+1].first)>=0) {
				ans-=2;
				S[1].erase(it);
				continue;
			}
			S[0].insert(max(i+1,P[2*i+1].first));
		}
	}
	cout<<ans<<'\n';
	return 0;
}

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