Submission #1233916

#TimeUsernameProblemLanguageResultExecution timeMemory
1233916ByeWorldCoin Collecting (JOI19_ho_t4)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define fi first
#define se second
#define lf ((id<<1))
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define pb push_back
using namespace std;
const int MAXN = 3e5+10;
const int INF = 1e9+10;
const int LOG = 20;
int MOD;
typedef pair<int,int> pii;

int sum(int a, int b){ return (a+MOD+b)%MOD; }
void chsum(int &a, int b){ a = sum(a,b); }
int mul(int a, int b){ return (a*b)%MOD; }
int expo(int a, int b){ 
	if(b==0) return 1;
	int te = expo(a, b>>1); te = mul(te,te);
	return (b%2 ? (a*te)%MOD : te); 
}
void chmul(int &a, int b){ a = mul(a,b); }
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }

int n, a[MAXN], b[MAXN], cnt[MAXN][5];
int ans;

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	vector<int> cc;
	for(int i=1; i<=2*n; i++){
		cin>>a[i]>>b[i];
		cc.pb(a[i]);
	}
	sort(cc.begin(), cc.end());
	// cout << ans << " ans\n";
	set<pii>zer, isi; // salah satu
	int las = 0, p = 0;
	for(int i=1; i<=n; i++){
		int tot = 0;
		while(tot<2){
			if(!isi.empty()){
				ans += abs(i - (*isi.begin()).fi );
				isi.erase(isi.begin());
			} else {
				zer.insert({i, ++p});
			}
			tot++; 
		}
		while(las<cc.size() && cc[las]<=i){
			if(!zer.empty()){
				ans += abs(cc[las] - (*zer.begin()).fi );
				zer.erase(zer.begin());
			} else {
				isi.insert({cc[las], ++p});
			}
			las++;
		}

		
		if(i==n){
			while(las<cc.size()){
				if(!zer.empty()){
					ans += abs(cc[las] - (*zer.begin()).fi );
					zer.erase(zer.begin());
				} else {
					isi.insert({cc[las], ++p});
				}
				las++;
			}
		}
	}

	cc.clear();
	for(int i=1; i<=2*n; i++) cc.pb(b[i]);
	sort(cc.begin(), cc.end());
	zer.clear(), isi.clear(); // salah satu
	las = 0, p = 0;
	for(int i=1; i<=2; i++){
		int tot = 0;
		while(tot<n){
			if(!isi.empty()){
				ans += abs(i - (*isi.begin()).fi );
				isi.erase(isi.begin());
			} else {
				zer.insert({i, ++p});
			}
			tot++; 
		}
		while(las<cc.size() && cc[las]<=i){
			if(!zer.empty()){
				ans += abs(cc[las] - (*zer.begin()).fi );
				zer.erase(zer.begin());
			} else {
				isi.insert({cc[las], ++p});
			}
			las++;
		}

		
		if(i==2){
			while(las<cc.size()){
				if(!zer.empty()){
					ans += abs(cc[las] - (*zer.begin()).fi );
					zer.erase(zer.begin());
				} else {
					isi.insert({cc[las], ++p});
				}
				las++;
			}
		}
	}
	cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...