Submission #892033

#	Time	Username	Problem	Language	Result	Execution time	Memory
892033		vjudge1	전선 연결 (IOI17_wiring)	C++17	13 / 100	104 ms	15144 KiB

wiring

#include "wiring.h"

#include <bits/stdc++.h>

using namespace std;

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

template<class T>
struct bivec {
    vector<T> neg, poz;
    bivec(int sz, T v0) : neg(sz, v0), poz(sz, v0) {}
    T &operator[](ll p) {
        if(p >= 0) return poz[p];
        return neg[-p - 1];
    }
};


struct AIB {
    ll n;
    vll V;
    AIB(ll N) : n(N), V(2 * N + 3, 0) {}
    
    void update(ll p, ll v) {
        p += n + 1;
        while(p < V.size()) {
            V[p] += v;
            p += p & -p;
        }
    }

    ll query(ll p) {
        p += n + 1;
        ll re = 0;
        while(p) {
            re += V[p];
            p -= p & -p;
        }
        return re;
    }

    ll query(ll st, ll dr) {
        return query(dr) - query(st - 1);
    }

};

ll min_total_length(vi r, vi b) {
    ll n = r.size(), m = b.size();
    vector<ii> V;
    for(auto it : r)
        V.push_back({it, 1});
    for(auto it : b)
        V.push_back({it, -1});
    sort(V.begin(), V.end());
    const ll INF = 1e18;

    ll len = n + m;
    AIB delta(len);

    ll orig = 0, slope0 = 0, ult = -1;
    ll re = 0;

    set<pair<int, ll> > D;
    slope0 = -1e9;
    delta.update(orig, 2e9);
    D.insert({orig, 2e9});
    ll ref = 0;


    for(auto [it, cul] : V) {
        if(ult != -1) {
            D.insert({orig, 2 * (it - ult)});
            delta.update(orig, 2 * (it - ult));
            slope0 -= it - ult;
        }
        if(cul == -1) {
            re += (delta.query(orig) + slope0);
            orig++;
        } else {
            orig--;
            re -= (delta.query(orig) + slope0);
        }
        if(cul == 1) {

            ll sl = slope0;
            ///voi sterge un sufix
            while(!D.empty()) {
                auto [p, v] = *D.rbegin();
                sl = slope0 + delta.query(-len, p);
                if(sl > 0) {
                    D.erase({p, v});
                    delta.update(p, -v);
                    if(sl - v < 0) {
                        D.insert({p, v - sl});
                        delta.update(p, v - sl);
                    }
                } else {
                    break;
                }
            }

//            for(ll i = -len; i < len; ++i) {
//                sl += delta.query(i, i);
//                if(sl > 0) {
//                    delta.update(i, -sl);
//                    sl = 0;
//                }
//            }

        } else {
            ///voi sterge un prefix
            while(!D.empty()) {
                auto [p, v] = *D.begin();
                ll sl = slope0 + delta.query(-len, p - 1);
                if(sl < 0) {
                    D.erase({p, v});
                    slope0 += v;
                    delta.update(p, -v);
                    if(p > orig) {
                        re += (p - orig) * (- v);
                    }
                    if(v + sl > 0) {
                        slope0 -= v + sl;
                        delta.update(p, v + sl);
                        D.insert({p, v + sl});
                        if(p > orig) {
                            re += (p - orig) * (v + sl);
                        }
                    }
                } else {
                    break;
                }
            }

//            ll sl = slope0 + delta.query(-len, len);
//            for(ll i = len; i > -len; --i) {
//                sl -= delta.query(i, i);
//                if(sl < 0) {
//                    delta.update(i, sl);
//                    if(i > orig) {
//                        re += (i - orig) * sl;
//                    }
//                    slope0 -= sl;
//                    sl = 0;
//                }
//            }
        }
        ult = it;

   //     ll v = re;
   //     for(ll i = orig - 1; i >= -len; --i) {
   //         v -= delta.query(-len, i) + slope0;
   //     }
   //     for(ll i = -len; i <= len; ++i) {
   //         if(i == orig)  {
   //             cout << "(" << v << ") ";
   //         }
   //         else
   //             cout << v << " ";
   //         v += delta.query(-len, i) + slope0;
   //     }
   //     cout << "\n";
    }
    return re;
//    ll orig = 0;
//    bivec<ll> dp(n + m + 5, INF);
//    dp[0] = 0;
//    int ult = -1, len = n + m + 1;
//    for(auto [it, cul] : V) {
//        if(ult != -1) {
//            for(int i = -len; i <= len; ++i) {
//                dp[i] += abs(i - orig) * (it - ult);
//            }
//            orig -= cul;
//        }
//        ult = it;
//        if(cul == 1) {
//            for(int i = -len; i < len; ++i)
//                dp[i + 1] = min(dp[i + 1], dp[i]);
//        } else {
//            for(int i = len; i > -len; --i)
//                dp[i - 1] = min(dp[i - 1], dp[i]);
//        }
//
//        for(int i = -len; i <= len; ++i) {
//            string s = to_string(dp[i]);
//            if(dp[i] == INF) s = "INF";
//            if(i == orig)
//                cout << "(" << s << ") ";
//            else
//                cout << s << " ";
//        }
//        cout << "\n";
//    }
//    return dp[orig];
}

Compilation message (stderr)

wiring.cpp: In member function 'void AIB::update(ll, ll)':
wiring.cpp:30:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         while(p < V.size()) {
      |               ~~^~~~~~~~~~
wiring.cpp: In function 'll min_total_length(vi, vi)':
wiring.cpp:60:14: warning: unused variable 'INF' [-Wunused-variable]
   60 |     const ll INF = 1e18;
      |              ^~~
wiring.cpp:72:8: warning: unused variable 'ref' [-Wunused-variable]
   72 |     ll ref = 0;
      |        ^~~

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