oj.uz

Submission #233632

# Submission time Handle Problem Language Result Execution time Memory
233632 2020-05-21T06:22:27 Z balbit Palembang Bridges (APIO15_bridge) C++14
100 / 100
 1484 ms 124388 KB 
#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
*/

Compilation message

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 11 ms 10656 KB Output is correct
4 Correct 12 ms 10880 KB Output is correct
5 Correct 12 ms 10752 KB Output is correct
6 Correct 12 ms 10624 KB Output is correct
7 Correct 12 ms 10752 KB Output is correct
8 Correct 11 ms 10752 KB Output is correct
9 Correct 12 ms 10752 KB Output is correct
10 Correct 11 ms 10624 KB Output is correct
11 Correct 12 ms 10752 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 11 ms 10624 KB Output is correct
4 Correct 12 ms 10752 KB Output is correct
5 Correct 12 ms 10752 KB Output is correct
6 Correct 11 ms 10624 KB Output is correct
7 Correct 12 ms 10752 KB Output is correct
8 Correct 12 ms 10880 KB Output is correct
9 Correct 12 ms 10752 KB Output is correct
10 Correct 11 ms 10624 KB Output is correct
11 Correct 12 ms 10880 KB Output is correct
12 Correct 112 ms 101716 KB Output is correct
13 Correct 409 ms 115428 KB Output is correct
14 Correct 206 ms 92516 KB Output is correct
15 Correct 219 ms 72296 KB Output is correct
16 Correct 116 ms 101824 KB Output is correct
17 Correct 241 ms 115432 KB Output is correct
18 Correct 176 ms 111076 KB Output is correct
19 Correct 289 ms 114988 KB Output is correct
20 Correct 124 ms 101824 KB Output is correct
21 Correct 243 ms 115456 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 11 ms 9728 KB Output is correct
3 Correct 11 ms 9856 KB Output is correct
4 Correct 11 ms 9856 KB Output is correct
5 Correct 11 ms 9856 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 10 ms 9856 KB Output is correct
8 Correct 11 ms 9856 KB Output is correct
9 Correct 10 ms 9856 KB Output is correct
10 Correct 13 ms 9984 KB Output is correct
11 Correct 10 ms 9856 KB Output is correct
12 Correct 11 ms 9856 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 11 ms 9856 KB Output is correct
4 Correct 12 ms 9856 KB Output is correct
5 Correct 10 ms 9856 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 10 ms 9856 KB Output is correct
8 Correct 11 ms 9856 KB Output is correct
9 Correct 11 ms 9856 KB Output is correct
10 Correct 11 ms 9856 KB Output is correct
11 Correct 10 ms 9856 KB Output is correct
12 Correct 11 ms 9856 KB Output is correct
13 Correct 11 ms 10624 KB Output is correct
14 Correct 12 ms 10624 KB Output is correct
15 Correct 18 ms 10880 KB Output is correct
16 Correct 11 ms 9984 KB Output is correct
17 Correct 11 ms 10240 KB Output is correct
18 Correct 14 ms 10240 KB Output is correct
19 Correct 11 ms 10624 KB Output is correct
20 Correct 18 ms 10880 KB Output is correct
21 Correct 15 ms 10752 KB Output is correct
22 Correct 18 ms 10880 KB Output is correct
23 Correct 13 ms 10624 KB Output is correct
24 Correct 19 ms 10880 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 11 ms 9728 KB Output is correct
3 Correct 10 ms 9856 KB Output is correct
4 Correct 12 ms 9856 KB Output is correct
5 Correct 11 ms 9856 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 10 ms 9856 KB Output is correct
8 Correct 11 ms 9856 KB Output is correct
9 Correct 11 ms 9856 KB Output is correct
10 Correct 12 ms 9856 KB Output is correct
11 Correct 10 ms 9856 KB Output is correct
12 Correct 11 ms 9856 KB Output is correct
13 Correct 11 ms 10624 KB Output is correct
14 Correct 12 ms 10752 KB Output is correct
15 Correct 20 ms 10880 KB Output is correct
16 Correct 11 ms 9984 KB Output is correct
17 Correct 12 ms 10240 KB Output is correct
18 Correct 13 ms 10240 KB Output is correct
19 Correct 11 ms 10624 KB Output is correct
20 Correct 18 ms 10880 KB Output is correct
21 Correct 16 ms 10880 KB Output is correct
22 Correct 20 ms 10880 KB Output is correct
23 Correct 11 ms 10624 KB Output is correct
24 Correct 17 ms 10880 KB Output is correct
25 Correct 104 ms 97728 KB Output is correct
26 Correct 146 ms 100032 KB Output is correct
27 Correct 1325 ms 122344 KB Output is correct
28 Correct 1480 ms 124224 KB Output is correct
29 Correct 1484 ms 124168 KB Output is correct
30 Correct 698 ms 70504 KB Output is correct
31 Correct 117 ms 101052 KB Output is correct
32 Correct 1149 ms 124216 KB Output is correct
33 Correct 450 ms 119524 KB Output is correct
34 Correct 1174 ms 123596 KB Output is correct
35 Correct 121 ms 101064 KB Output is correct
36 Correct 987 ms 124388 KB Output is correct
37 Correct 98 ms 96344 KB Output is correct