oj.uz

Submission #233633

# Submission time Handle Problem Language Result Execution time Memory
233633 2020-05-21T06:28:46 Z balbit Palembang Bridges (APIO15_bridge) C++14
100 / 100
 1501 ms 124112 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;

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);
	         else MO(tree[i].r,mid+1,r,num,v);
}

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;
    }
    ll mid = (l+r)/2;
    QU(tree[o].l, l,mid, L, R);
    QU(tree[o].r,mid+1,r, L, R);
}

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

map<ll, int> segmp;

ll C(ll l, ll 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;
    re += (L+1) * (l) - (rps[L+1]);

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

    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;

vector<int> smawk(vector<int> row, vector<int> col){
    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)) {
        vector<int> nc;
        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);
        }
        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) {
        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));
        vector<int> lol = smawk(r,c);
        for (int x : lol) bug(x);
        bug(RE);
        cout<<re + RE*2 + n<<endl;
    }

}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:259: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 10672 KB Output is correct
4 Correct 15 ms 10928 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 10880 KB Output is correct
8 Correct 12 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 10880 KB Output is correct
8 Correct 12 ms 10752 KB Output is correct
9 Correct 12 ms 10880 KB Output is correct
10 Correct 11 ms 10624 KB Output is correct
11 Correct 12 ms 10752 KB Output is correct
12 Correct 109 ms 101080 KB Output is correct
13 Correct 441 ms 114864 KB Output is correct
14 Correct 209 ms 91748 KB Output is correct
15 Correct 230 ms 71532 KB Output is correct
16 Correct 116 ms 101180 KB Output is correct
17 Correct 223 ms 114660 KB Output is correct
18 Correct 182 ms 110308 KB Output is correct
19 Correct 281 ms 114148 KB Output is correct
20 Correct 119 ms 101104 KB Output is correct
21 Correct 244 ms 114660 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 10 ms 9728 KB Output is correct
3 Correct 10 ms 9856 KB Output is correct
4 Correct 11 ms 9856 KB Output is correct
5 Correct 10 ms 9856 KB Output is correct
6 Correct 10 ms 9856 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 14 ms 9856 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 10 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 11 ms 9856 KB Output is correct
10 Correct 11 ms 9856 KB Output is correct
11 Correct 11 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 10 ms 9984 KB Output is correct
17 Correct 11 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 13 ms 10752 KB Output is correct
22 Correct 19 ms 10880 KB Output is correct
23 Correct 11 ms 10624 KB Output is correct
24 Correct 18 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 10 ms 9728 KB Output is correct
3 Correct 10 ms 9856 KB Output is correct
4 Correct 11 ms 9984 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 10 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 10 ms 9984 KB Output is correct
17 Correct 11 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 13 ms 10752 KB Output is correct
22 Correct 19 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 106 ms 97672 KB Output is correct
26 Correct 143 ms 99776 KB Output is correct
27 Correct 1289 ms 122212 KB Output is correct
28 Correct 1463 ms 124112 KB Output is correct
29 Correct 1501 ms 124004 KB Output is correct
30 Correct 688 ms 70252 KB Output is correct
31 Correct 116 ms 101180 KB Output is correct
32 Correct 1138 ms 124028 KB Output is correct
33 Correct 446 ms 119416 KB Output is correct
34 Correct 1199 ms 123168 KB Output is correct
35 Correct 117 ms 101060 KB Output is correct
36 Correct 1008 ms 124068 KB Output is correct
37 Correct 103 ms 96868 KB Output is correct