제출 #586808

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
586808		MohamedFaresNebili	전선 연결 (IOI17_wiring)	C++14	13 / 100	44 ms	8016 KiB

wiring

#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

        using namespace std;

        using ll = long long;
        using ii = pair<ll, ll>;
        using vi = vector<int>;

        #define ff first
        #define ss second
        #define pb push_back
        #define all(x) (x).begin(), (x).end()
        #define lb lower_bound

        const int MOD = 1000 * 1000 * 1000 + 7;

        ll min_total_length(vector<int> R, vector<int> B) {
            ll N = R.size(), M = B.size(), res = 0;
            vector<pair<ll, ll>> A;
            for(int l = 0; l < N; l++) A.pb(make_pair(R[l], 0));
            for(int l = 0; l < M; l++) A.pb(make_pair(B[l], 1));
            sort(A.begin(), A.end()); stack<ll> U, V;

            for(int l = 0; l < N + M; l++) {
                ii P = A[l];
                if(P.ss == 1) {
                    if(V.empty()) {
                        U.push(A[l].ff);
                        continue;
                    }
                    res += ll(A[l].ff - V.top()); V.pop();
                    continue;
                }
                if(U.empty()) {
                    V.push(A[l].ff);
                    continue;
                }
                res += ll(A[l].ff - U.top()); U.pop();
            }

            while(!U.empty()) {
                auto it = lb(R.begin(), R.end(), U.top());
                ll ans = 1e18 + 7;
                if(it != R.end()) ans = min(ans, abs(*it - U.top()));
                if(it != R.begin()) it--, ans = min(ans, abs(*it - U.top()));
                res += ans; U.pop();
            }
            while(!V.empty()) {
                auto it = lb(B.begin(), B.end(), V.top());
                ll ans = 1e18 + 7;
                if(it != B.end()) ans = min(ans, abs(*it - V.top()));
                if(it != B.begin()) it--, ans = min(ans, abs(*it - V.top()));
                res += ans; V.pop();
            }
            return res;
        }

• Subtask 1: 0 / 7
• Subtask 2: 13 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45