제출 #978691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
978691		GrindMachine	전선 연결 (IOI17_wiring)	C++17	100 / 100	130 ms	13240 KiB

wiring

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

slope trick solution
knew the solution idea beforehand

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "wiring.h"

struct SlopeTrick{
    ll l,r,dir;
    ll first_pos,first_val;
    priority_queue<ll,vector<ll>,greater<ll>> pq;

    SlopeTrick(ll l_, ll r_, ll dir_){
        l = l_, r = r_, dir = dir_;
        if(dir == 1) first_pos = l;
        else first_pos = r;
        first_val = inf2;
    }

    void min_conv(vector<pair<ll,ll>> v){
        if(l == r){
            for(auto [x,y] : v){
                if(x == 0){
                    first_val += y;
                }
            }

            return;
        }

        if(first_val >= inf2) return;

        if(dir == 1){
            pq.push(v[1].ss-v[0].ss);
            first_val += v[0].ss;
            first_pos += v[0].ff;

            while(first_pos < l){
                first_val += pq.top();
                pq.pop();
                first_pos++;
            }
        }
        else{
            pq.push(v[0].ss-v[1].ss);
            first_val += v[1].ss;
            first_pos += v[1].ff;

            while(first_pos > r){
                first_val += pq.top();
                pq.pop();
                first_pos--;
            }
        }
    }

    void upd(ll x){
        if(x > first_val) return;
        ll sub = first_val-x;
        first_val = x;
        if(!pq.empty()){
            ll mn = pq.top();
            pq.pop();
            pq.push(mn+sub);
        }
    }
};

long long min_total_length(std::vector<int> a, std::vector<int> b) {
    ll n = sz(a), m = sz(b);
    sort(all(a)), sort(all(b));

    vector<array<ll,3>> c;
    
    rep(i,n){
        ll x = a[i];
        auto it = lower_bound(all(b),x);
        ll bef = -inf2, aft = inf2;
        if(it != b.end()) aft = *it;
        if(it != b.begin()) bef = *prev(it);
        ll mn_dis = min(abs(x-bef),abs(x-aft));
        c.pb({x,mn_dis,1});         
    }

    rep(i,m){
        ll x = b[i];
        auto it = lower_bound(all(a),x);
        ll bef = -inf2, aft = inf2;
        if(it != a.end()) aft = *it;
        if(it != a.begin()) bef = *prev(it);
        ll mn_dis = min(abs(x-bef),abs(x-aft));
        c.pb({x,mn_dis,2});
    }
    
    sort(all(c));

    SlopeTrick small(-inf1,-1,-1), med(0,0,1), big(1,inf1,1);
    med.upd(0);

    for(auto [x,y,t] : c){
        if(t == 1){
            // red
            // small: min conv with (0,y),(1,x)
            // med:   min conv with (0,y),(1,-x)
            // big:   min conv with (0,y),(1,-x)

            ll small_to_med = small.first_val+x;
            ll med_to_big = med.first_val-x;

            small.min_conv({{0,y},{1,x}});
            med.min_conv({{0,y},{1,-x}});
            big.min_conv({{0,y},{1,-x}});

            med.upd(small_to_med);
            big.upd(med_to_big);
        }
        else{
            // blue
            // small: min conv with (-1,-x),(0,y)
            // med:   min conv with (-1,-x),(0,y)
            // big:   min conv with (-1,x),(0,y)

            ll big_to_med = big.first_val+x;
            ll med_to_small = med.first_val-x;

            small.min_conv({{-1,-x},{0,y}});
            med.min_conv({{-1,-x},{0,y}});
            big.min_conv({{-1,x},{0,y}});

            med.upd(big_to_med);
            small.upd(med_to_small);
        }

        // vector<ll> v;
        // auto curr = big.pq;
        // while(!curr.empty()){
        //     v.pb(curr.top());
        //     curr.pop();
        // }
        // debug(big.first_val);
        // debug(v);

        // debug(small.first_val);
        // debug(med.first_val);
        // debug(big.first_val);
        // cout << endl;
    }

    ll ans = med.first_val;
    ll oans = -1;

    // {
    //     ll siz = sz(c);
    //     c.insert(c.begin(),{0,0});
     
    //     vector<ll> p(siz+5), pref(siz+5);
    //     rep1(i,siz){
    //         p[i] = p[i-1], pref[i] = pref[i-1];
    //         if(c[i][2] == 1) p[i]++, pref[i] += c[i][0];
    //         else p[i]--, pref[i] -= c[i][0];
    //     }
     
    //     vector<ll> dp(siz+5,inf2);
    //     vector<ll> prev_occ(2*siz+5,-1);
    //     dp[0] = 0;
    //     prev_occ[siz] = 0;
     
    //     rep1(i,siz){
    //         dp[i] = dp[i-1]+c[i][1];
    //         if(prev_occ[p[i]+siz] != -1){
    //             ll j = prev_occ[p[i]+siz];
    //             ll diff = pref[i]-pref[j];
    //             amin(dp[i],dp[j]+abs(diff));
    //         }
     
    //         prev_occ[p[i]+siz] = i;
    //     }

    //     oans = dp[siz];
    // }

    // debug(ans,oans);
    // assert(ans == oans);

    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:205:8: warning: unused variable 'oans' [-Wunused-variable]
  205 |     ll oans = -1;
      |        ^~~~

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