Submission #1310147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310147		zxzuam	Coin Collecting (JOI19_ho_t4)	C++20	0 / 100	1 ms	576 KiB

joi2019_ho_t4

#include<bits/stdc++.h>
#define int long long
#define I128 //||is_same<T,__int128_t>::value||is_same<T,__uint128_t>::value
using namespace std;
template<typename T>enable_if_t<is_integral<T>::value I128,void> readmain(T &x)
{
	bool neg=false;int c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')neg=true;
	for(x=0;isdigit(c);c=getchar())x=(T)(10*x+(c-'0'));
	if(neg)x=-x;
}
template<typename T>T& read(T &x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &x,Tr&... r){readmain(x);read(r...);}
constexpr int maxn = 2e5 + 9, mod = 1e9 + 7, L = 1e8;

void solve(){
    int n;
    read(n);
    vector <int> x(2 * n + 1), y(2 * n + 1);
    for(int i = 1; i <= 2 * n; i++) {
        read(x[i], y[i]);
    }
    int ans = 0;
    for(int i = 1; i <= 2 * n; i++) {
        if(1 <= x[i] && x[i] <= n) {
            if(2 <= y[i]){
                ans += y[i] - 2ll;
                y[i] = 2;
            }
            else{
                ans += 1ll - y[i];
                y[i] = 1;
            }
        }
        else{
            if(2 <= y[i]) {
                ans += y[i] - 2ll;
                y[i] = 2;
            }
            else{
                ans += 1ll - y[i];
                y[i] = 1;
            }
            if(x[i] < 1) {
                ans += 1ll - x[i];
                x[i] = 1;
            }
            else{
                ans += x[i] - n;
                x[i] = n;
            }
        }
    }
    multiset <int> s1, s2;
    for(int i = 1; i <= 2 * n; i++) {
        if(y[i] == 1) {
            s1.insert(x[i]);
        }
        else{
            s2.insert(x[i]);
        }
    }
    for(int i = 1; i <= 2 * n; i++) {
        int X = (i + 1) / 2, Y = i & 1;
        if(!Y){
            Y = 2;
        }
        int l1 = mod, r1 = mod;
        int l2 = mod, r2 = mod;
        if(!s1.empty()){
            auto it = lower_bound(s1.begin(), s1.end(), X);
            if(it != s1.end()){
                r1 = *it;
                r1 = abs(r1 - X);
            }
            if(it != s1.begin()){
                it--;
                l1 = *it;
                l1 = abs(l1 - X);
            }
        }
        if(!s2.empty()) {
            auto it = lower_bound(s2.begin(), s2.end(), X);
            if(it != s2.end()) {
                r2 = *it;
                r2 = abs(r2 - X);
            }
            if(it != s2.begin()){
                it--;
                l2 = *it;
                l2 = abs(l2 - X);
            }
        }
        if(Y == 1) {
            l2++;
            r2++;
        }
        if(Y == 2){
            l1++;
            r1++;
        }
        int mn = min({l1, r1, l2, r2});
        ans += mn;
        if(mn == l1) {
            auto it = lower_bound(s1.begin(), s1.end(), X);
            it--;
            s1.erase(it);
        }
        else if(mn == r1){
            auto it = lower_bound(s1.begin(), s1.end(), X);
            s1.erase(it);
        }
        else if(mn == l2){
            auto it = lower_bound(s2.begin(), s2.end(), X);
            it--;
            s2.erase(it);
        }
        else{
            auto it = lower_bound(s2.begin(), s2.end(), X);
            s2.erase(it);
        }
    }
    printf("%lld", ans);
}

int32_t main(){
    //ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    int tt = 1;
    //cin >> tt;
    while(tt--) {
        solve();
    }
}

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