제출 #233632

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

bridge

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#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{
    int l=0,r=0;
    ll val=0;
    int sz=0;
} tree [maxn<<6];
int T_cnt = 0;

//inline ll getval(node *&o){return o?o->val:0;}
//inline int getsz(node *&o){return o?o->sz:0;}
//
void build(int &o, int l, int r) {
    o = T_cnt++;
    if (l == r) {
        return;
    }
    int mid = (l+r)/2;
    build(tree[o].l,l,mid);
    build(tree[o].r,mid+1,r);
}

inline void MO(int &i,int l,int r, ll num, ll v)                     //&的神奇功能，会把外面传入变量一起改变
{
	tree[T_cnt++]=tree[i];                                         //先继承上一棵树的信息
	i=T_cnt-1;                                                     //修改子树关系
	++tree[i].sz;
	tree[i].val += v;
	if (l==r) return;
	int mid=(l+r)>>1;
	if (num<=mid) MO(tree[i].l,l,mid,num,v);                     //小于等于mid则在左边更新，右边直接与上一棵树共用
	         else MO(tree[i].r,mid+1,r,num,v);                   //大于mid，左边更新，右边共用
//    tree[i].sz = tree[i].l.sz + tree[i].r.sz;
//    tree[i].val = tree[i].l.val + tree[i].r.val;
}

ll A=0, B=0;

void QU(int o, int l, int r, int L, int R) {
    if (l > R || r<L) return;
    if (l>=L && r <=R) {
        A += tree[o].val; B += tree[o].sz;
        return;
//        tree[o].val, tree[o].sz;
    }
    ll mid = (l+r)/2;
    QU(tree[o].l, l,mid, L, R);
    QU(tree[o].r,mid+1,r, L, R);
//    return {A.f+B.f, A.s+B.s};
}

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

map<ll, int> segmp;

ll C(ll l, ll r) {
//    return matrix[l][r];
    // if (l>r) return 10000000000000000ll;
    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);

    auto sit = segmp.lower_bound(r+l);

    A=B=0;
    QU(lhistory[lat+1], 0, 1e5+3, 0, (*prev(sit)).s);
    re += A - B * l;

    A=B=0;
    QU(rhistory[rat+1], 0, 1e5+3, (*(sit)).s, 1e5+3);
    re += B*r-A;

    return re;
}

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


vector<int> smawk(vector<int> row, vector<int> col){
    bug("SMAWK!", SZ(row), SZ(col));
#ifdef BALBIT
    cout<<"R: "; for (int x : row) cout<<x<<' ';
    cout<<endl;
    cout<<"C: "; for (int x : col) cout<<x<<' ';
    cout<<endl;
#endif
    if (SZ(col) <= 4) {
        vector<int> ret;
        for (int i = 0; i<SZ(row); ++i){
            ll mybest = 1e18+2;
            ret.pb(0);
            for (int j = 0; j<SZ(col); ++j) {
                ll cc = C(row[i], col[j]);
                if (cc < mybest) {
                    ret.back() = col[j];
                    mybest = cc;
                }
            }
            RE=min(RE,mybest);
        }
        return ret;
    }
    if (SZ(col) > SZ(row)) {
        // Reduce!
        vector<int> nc;  // Stack of surviving columns
        for (ll cc : col) {
            while (true) {
                if (nc.size() == 0) break;
                ll rr = row[nc.size() - 1];
                if (C(rr, cc) > C(rr, nc.back()))
                    break;
                nc.pop_back();
            }
            if (nc.size() < row.size())
                nc.push_back(cc);
        }
#ifdef BALBIT

#endif
        return smawk(row, nc);
    }else{
        vector<int> odds;
        for (int i = 1; i<SZ(row); i += 2) {
            odds.pb(row[i]);
        }
        vector<int> pos = smawk(odds, col);
        pos.pb(col.back());
        vector<int> ret;
        int j = 0;
        for (int i = 0; i<SZ(row); i++) {
            if (i & 1) {
                ret.pb(pos[i/2]);
            }else{
                ret.pb(col[j]);
                ll mybest = 1e18+2;
                for (int k = j; k < SZ(col) && col[k] >= pos[i/2]; ++k) {
                    ll cc = C(row[i], col[k]);
                    if (cc < mybest) {
                        mybest = cc; ret.back() = col[k];
                    }
                    j=k;
                }
                RE = min(RE, mybest);
            }
        }
        return ret;
    }

}


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(0); rhistory.pb(0);
    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;
    build(lhistory.back(), 0, 1e5+3);
    for (int i = 0; i<n; ++i) {
        int topb = T_cnt;
        int tmp = lhistory.back();
        MO(tmp, 0, 1e5+3, segmp[v[i].f+v[i].s], v[i].f);
        lhistory.pb(topb);
    }
    sort(ALL(v), [&](pii a, pii b){return a.s<b.s;});
    build(rhistory.back(), 0, 1e5+3);
    bug(rhistory.back());
    for (int i = 0; i<n; ++i) {
//        if (v[i].s == 6) bug(v[i].s, v[i].f+v[i].s);
        int topb = T_cnt;
        int tmp = rhistory.back();
        MO(tmp, 0, 1e5+3, segmp[v[i].f+v[i].s], v[i].s);
        rhistory.pb(topb);
    }
    bug(rhistory.back());
    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];
    }

    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;
        }
        cout<<re + ans*2 + n<<endl;
    }else{



         m = SZ(hv);
         p.resize(m);
         RE = C(0,0);

        int _it = 0;
        vector<int> r;
        for (pii ele : hv) {
            p[_it++] = ele.f;
            r.pb(ele.f);
            bug(ele.f);
        }
        vector<int> c = r;
        reverse(ALL(c));
        reverse(ALL(r));

#ifdef BALBIT
        for (int i = 0; i<SZ(r); ++i) {
            for (int j = 0; j<SZ(c); ++j) {
                cout<<C(r[i],c[j])<<' ';
            }
            cout<<endl;
        }
#endif
        vector<int> lol = smawk(r,c);
        for (int x : lol) bug(x);
        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
*/

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

bridge.cpp: In function 'int main()':
bridge.cpp:297:18: warning: unused variable 'x' [-Wunused-variable]
         for (int x : lol) bug(x);
                  ^

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