Submission #110303

#	Time	Username	Problem	Language	Result	Execution time	Memory
110303		polyfish	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	123 ms	8440 KiB

joi2019_ho_t4

//Pantyhose(black) + glasses = infinity

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int64_t _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int64_t _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "coincollecting"

const int64_t MAX_N = 200002;
const int64_t INF = 1e18;

int64_t n, cnt[3][MAX_N];
int64_t res;
pair<int64_t, int64_t> a[MAX_N];

void read_input() {
    cin >> n;

    for (int64_t i=1; i<=2*n; ++i)
        cin >> a[i].second >> a[i].first;
}

void init() {
    for (int64_t i=1; i<=2*n; ++i) {
        vector<int64_t> p = {1, n};
        if (0<a[i].second && a[i].second<=n)
            p.push_back(a[i].second);

        int64_t d = INF;

        for (int64_t x=1; x<=2; ++x) {
            for (auto y : p)
                d = min(d, abs(a[i].first-x)+abs(a[i].second-y));
        }

        res += d;

        for (int64_t x=1; x<=2; ++x) {
            for (auto y : p) {
                if (d==abs(a[i].first-x)+abs(a[i].second-y)) {
                    ++cnt[x][y];
                    break;
                }
            }
        }
    }
}

void solve() {
    int64_t u = 0, d = 0;

    for (int64_t i=1; i<=n; ++i) {
        u += (cnt[1][i]-1);
        d += (cnt[2][i]-1);

        while (d>0 && u<0) {
            --d;
            ++u;
            ++res;
        }

        while (d<0 && u>0) {
            ++d;
            --u;
            ++res;
        }

        res = res + abs(u) + abs(d);
    }
}

int main() {
	#ifdef GLASSES_GIRL
		freopen(FILE_NAME".in", "r", stdin);
//		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);

	read_input();
	init();
	solve();
	cout << res;
}

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