oj.uz

Submission #203812

# Submission time Handle Problem Language Result Execution time Memory
203812 2020-02-22T08:58:15 Z kig9981 Coin Collecting (JOI19_ho_t4) C++17
0 / 100
 5 ms 380 KB 
#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> L[2], R[2], 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) {
			bool chk=false;
			if(P[2*i].first<=i+1) {
				auto it=L[0].lower_bound(P[2*i].first);
				if(it!=L[0].end()) {
					L[0].erase(it);
					ans-=2;
					chk=true;
				}
				it=S[0].lower_bound(P[2*i].first);
				if(it!=S[0].end()) {
					S[0].erase(it);
					ans-=2;
					chk=true;
				}
			}
			else {
				auto it=R[0].lower_bound(i+1);
				if(it!=R[0].end()) {
					R[0].erase(it);
					ans-=2;
					chk=true;
				}
				it=S[0].lower_bound(i+1);
				if(it!=S[0].end()) {
					S[0].erase(it);
					ans-=2;
					chk=true;
				}
			}
			if(!chk) {
				if(P[2*i].first<i+1) L[1].insert(i+1);
				else if(P[2*i].first>i+1) R[1].insert(P[2*i].first);
				else S[1].insert(i+1);
			}
		}
		if(P[2*i+1].second<2) {
			if(P[2*i+1].first<=i+1) {
				auto it=L[1].lower_bound(P[2*i+1].first);
				if(it!=L[1].end()) {
					L[1].erase(it);
					ans-=2;
					continue;
				}
				it=S[1].lower_bound(P[2*i+1].first);
				if(it!=S[1].end()) {
					S[1].erase(it);
					ans-=2;
					continue;
				}
			}
			else {
				auto it=R[1].lower_bound(i+1);
				if(it!=R[1].end()) {
					R[1].erase(it);
					ans-=2;
					continue;
				}
				it=S[1].lower_bound(i+1);
				if(it!=S[1].end()) {
					S[1].erase(it);
					ans-=2;
					continue;
				}
			}
			if(P[2*i+1].first<i+1) L[0].insert(i+1);
			else if(P[2*i+1].first>i+1) R[0].insert(P[2*i+1].first);
			else S[0].insert(i+1);
		}
	}
	cout<<ans<<'\n';
	return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 380 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Incorrect 4 ms 376 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 380 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Incorrect 4 ms 376 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 380 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Incorrect 4 ms 376 KB Output isn't correct
10 Halted 0 ms 0 KB -