제출 #232554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
232554		balbit	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	456 ms	134244 KiB

bridge

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

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<" - ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#endif // BALBIT

//#define int ll
#define pii pair<ll, ll>
#define f first
#define s second

#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x.size())
#define pb push_back

vector<pii> v;
int n;
const int maxn = 1e5+3;
vector<int> rbs, lbs;// right bounds and left bounds, separated and sorted
ll rps[maxn], lps[maxn];// right bounds and left bounds, separated and sorted and ps

struct node{
    node *lc=0, *rc=0;
    ll val=0;
    int sz=0;
} pool [10000000];
auto _ptr = pool;

inline ll getval(node *&o){return o?o->val:0;}
inline int getsz(node *&o){return o?o->sz:0;}

node* MO(node *o, ll l, ll r, ll p, int v) {
//    if (!o) o = new node();
    node * ret = new (_ptr++)node ();
    if (o) ret->lc = o->lc, ret->rc = o->rc, ret->val = o->val, ret->sz = o->sz;
//    ret -> val = o->val; ret->sz = o->sz;
    if (l == r) {
        bug(p);
        ret->val += v;
        ret->sz += 1;
//        if (ret->val == 20) bug(ret->val, ret->sz);
        return ret;
    }
//    if (!o->lc) o->lc = new node();
//    if (!o->rc) o->rc = new node();
    ll mid = (l+r)/2;
    if (p <= mid) {
        ret -> lc = MO(ret->lc, l, mid, p, v);
//        ret -> rc = o->rc;
    }
    else{
//        ret -> lc = o->lc;
        ret -> rc = MO(ret->rc, mid+1, r, p, v);
    }
    ret->val = getval(ret->lc) + getval(ret->rc);
    ret->sz = getsz(ret->lc) + getsz(ret->rc);
//    if (ret->val == 20) bug(ret->val, ret->sz);
    return ret;
}

pii QU(node *&o, ll l, ll r, int L, int R) {
     if (!o || l > R || r<L) return {0,0};
     if (l>=L && r <=R) return {o->val, o->sz};
     ll mid = (l+r)/2;
     pii A = QU(o->lc, l,mid, L, R);
     pii B = QU(o->rc,mid+1,r, L, R);
     return {A.f+B.f, A.s+B.s};
}

//void MOO(node *o, int l, int r, int p, int v) {
//    if (o == nullptr) o = new node();
//    if (l == r) {
//        o->val = p;
//        return;
//    }
//    int mid = (l+r)/2;
//    if (p <= mid) {
//        o -> lc = MO(o->lc, l, mid, p, v);
//    }
//    else{
//        o -> rc = MO(o->rc, mid+1, r, p, v);
//    }
//    o->val = getval(o->lc) + getval(o->rc);
//    o->sz = getsz(o->lc) + getsz(o->rc);
//}

vector<node*> lhistory, rhistory;
vector<int> lrev;

map<ll, int> segmp;

ll C(ll l, ll r) {
    if (l>r) swap(l,r);
    int L = lower_bound(ALL(rbs), l) - rbs.begin() -1;// right bounds less than l
    int R = upper_bound(ALL(lbs), r) - lbs.begin();// right bounds less than l

    ll re = 0;
    re += (lps[n] - lps[R]) - (n-R) * r;
    bug(re);
    bug(L+1);
    re += (L+1) * (l) - (rps[L+1]);
    bug(re);

    int lat = lower_bound(ALL(lrev), l, greater<int>()) - lrev.begin() - 1;
    int rat = lower_bound(ALL(rbs),  r) - rbs.begin()-1;
    bug(lat, rat);

    pii lq = QU(lhistory[lat+1], 0, 1e5+3, 0, (*prev(segmp.lower_bound(r+l))).s);
    pii rq = QU(rhistory[rat+1], 0, 1e5+3, (*prev(segmp.upper_bound(r+l))).s, 1e5+3);

    bug(lq.f, lq.s, rq.f, rq.s);

    re += lq.f - lq.s * l;
    re += rq.s * r - rq.f;

    return re;
}

ll RE;
vector<int> p;
int m;
node * lroot = 0, *rroot = 0;

void go(int il, int ir, int jl, int jr) {
    if (il > ir || jl > jr) return;
    int mid = (il + ir)/2;
    int best = -1;
    ll bestval = 2e18+3;

    for (int j = jl; j<=jr; ++j) {
        ll tt = C(p[mid], p[j]);
        RE = min (RE, tt);
        if (tt < bestval) {
            best = j; bestval = tt;
        }
    }
    go(il, mid-1, jl, best);
    go(mid+1, ir, best, jr);

}

signed main(){
    IOS();
    int k; cin>>k>>n;
    ll re = 0;
    map<int, int> hv;
    for (int i = 0; i<n; ++i) {
        char x, x2;
        int l, r; cin>>x>>l>>x2>>r;
        re += abs(r-l);
        if (x == x2) {
        }else{
            if (r < l) swap(l,r);
            v.pb({l,r});
            rbs.pb(r);
            lbs.pb(l);
            hv[l]--;
            hv[r]--;
        }
    }
    n = SZ(v);
    lhistory.pb(nullptr);
    rhistory.pb(nullptr);
    sort(ALL(v), [&](pii a, pii b){return a.f>b.f;});
    vector<ll> fff;
    for (int i = 0; i<n; ++i) {
        fff.pb(v[i].f + v[i].s);
    }
    sort(ALL(fff));
    for (int i = 0; i<n; ++i) {
        segmp[fff[i]] = i;
    }
    segmp[-1]=-1;
    for (int i = 0; i<n; ++i) {
        lhistory.pb(MO(lhistory.back(), 0, 1e5+3, segmp[v[i].f+v[i].s], v[i].f));
    }
    sort(ALL(v), [&](pii a, pii b){return a.s<b.s;});
    for (int i = 0; i<n; ++i) {
//        if (v[i].s == 6) bug(v[i].s, v[i].f+v[i].s);
        rhistory.pb(MO(rhistory.back(), 0, 1e5+3, segmp[v[i].f+v[i].s], v[i].s));
    }
    sort(ALL(rbs));
    sort(ALL(lbs));
    lrev = lbs;
    sort(ALL(lrev), greater<int>());
    for (int i = 0; i<n; ++i) {
        rps[i+1] = rps[i] + rbs[i];
        lps[i+1] = lps[i] + lbs[i];
    }

//    int L, R;
//    while (cin>>L>>R) {
//        cout<<C(L, R)<<endl;
//    }
//
//    return 0;

    if (k == 1) {
        ll now = lps[n];
        bug(now);
        ll ans = now;
        ll x = 0;
        ll frt = n;
        for (pii ele : hv) {
            ll X = ele.f;
            now -= (X-x) * (frt);
            bug(X, now);
            ans = min(ans, now);
            frt += ele.s;
            x=X;
        }
//        if (ans == 1000000000000000ll) ans = 0;
        cout<<re + ans*2 + n<<endl;
    }else{
         m = SZ(hv);
         p.resize(m);
         RE = C(0,0);

        int _it = 0;
        for (pii ele : hv) {
            p[_it++] = ele.f;
        }
        go(0,m-1,0,m-1);
//        cout<<re + ans*2 + n<<endl;
        bug(RE);
        cout<<re + RE*2 + n<<endl;
    }

}
/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37