Submission #671175

#	Time	Username	Problem	Language	Result	Execution time	Memory
671175		fatemetmhr	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	141 ms	26312 KiB

bridge

// fikhshal chye daram code miznm :}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second

const int maxn5 = 3e5 + 10;

ll sumrbef[2], cntbef[2], sumlaf[2], cntaf[2], ans[2];
ll pref[maxn5], suf[maxn5];
ll ind[2], per[maxn5], l[maxn5], r[maxn5];
int idl[maxn5], idr[maxn5];
vector <int> st[maxn5], ft[maxn5], pt;

inline bool cmp(int i, int j){return l[i] + r[i] < l[j] + r[j];}

inline void add_seg(int id){
    id = per[id];
    st[idl[id]].pb(id);
    ft[idr[id]].pb(id);
    for(int t = 0; t < 2; t++) if(ind[t] >= 0 && ind[t] < pt.size()){
        ll ver = pt[ind[t]];
        if(r[id] < ver){
            cntbef[t]++;
            sumrbef[t] += r[id];
            ans[t] += ver - r[id];
        }
        else if(l[id] > ver){
            cntaf[t]++;
            sumlaf[t] += l[id];
            ans[t] += l[id] - ver;
        }
    }
    return;
}

inline void inc(){
    ind[1]++;
    if(ind[1] == pt.size())
        return;
    ll ver = pt[ind[1]];
    for(auto id : ft[ind[1] - 1]){
        cntbef[1]++;
        sumrbef[1] += r[id];
    }
    for(auto id : st[ind[1]]){
        cntaf[1]--;
        sumlaf[1] -= l[id];
    }
    ans[1] = cntbef[1] *  ver - sumrbef[1] + sumlaf[1] - cntaf[1] * ver;
}

inline void dec(){
    ind[1]--;
    if(ind[1] < 0)
        return;
    ll ver = pt[ind[1]];
    for(auto id : ft[ind[1]]){
        cntbef[1]--;
        sumrbef[1] -= r[id];
    }
    for(auto id : st[ind[1] + 1]){
        cntaf[1]++;
        sumlaf[1] += l[id];
    }
    ans[1] = cntbef[1] *  ver - sumrbef[1] + sumlaf[1] - cntaf[1] * ver;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); 

    int n, k; cin >> k >> n;
    ll all = 0;
    int m = 0;
    for(int i = 0; i < n; i++){
        char c1, c2;
        cin >> c1 >> l[i] >> c2 >> r[i];
        if(l[i] > r[i])
            swap(l[i], r[i]);
        all += r[i] - l[i];
        if(c1 != c2){
            all++;
            per[m++] = i;
            pt.pb(l[i]); pt.pb(r[i]);
        }
    }

    sort(all(pt));
    pt.resize(unique(all(pt)) - pt.begin());

    for(int i = 0; i < n; i++){
        idl[i] = lower_bound(all(pt), l[i]) - pt.begin();
        idr[i] = lower_bound(all(pt), r[i]) - pt.begin();
    }

    /*
    cout << "Points " << endl;

    for(auto u : pt)
        cout << u << ' ';
    cout << endl;
    */


    sort(per, per + m, cmp); // bar hasbe l + r;

    //for(int i = 0; i < m; i++)
    //    cout << "segment of " << per[i] << ' ' << l[per[i]] << ' ' << r[per[i]] << endl;

    sumrbef[0] = 0; cntbef[0] = 0; sumlaf[0] = 0; cntaf[0] = 0;
    sumrbef[1] = 0; cntbef[1] = 0; sumlaf[1] = 0; cntaf[1] = 0;
    ans[0] = ans[1] = 0;
    ind[0] = 0; ind[1] = 1;
    for(int i = 0; i < m; i++){
        add_seg(i);
        while(ind[1] < pt.size() && ans[0] > ans[1]){
            ind[0] = ind[1];
            sumrbef[0] = sumrbef[1];
            cntbef[0] = cntbef[1];
            sumlaf[0] = sumlaf[1];
            cntaf[0] = cntaf[1];
            ans[0] = ans[1];
            inc();
        }
        pref[i] = ans[0];
        //cout << i << ' ' << ind[0] << ' ' << ind[1] << ' '<< ans[0] << ' ' << ans[1] << endl;
    }

    //cout << "all " << all << endl;

    if(k == 1)
        return cout << pref[m - 1] * 2 + all << endl, 0;

    for(int i = 0; i < pt.size(); i++){
        st[i].clear();
        ft[i].clear();
    }


    sumrbef[0] = 0; cntbef[0] = 0; sumlaf[0] = 0; cntaf[0] = 0;
    sumrbef[1] = 0; cntbef[1] = 0; sumlaf[1] = 0; cntaf[1] = 0;
    ans[0] = ans[1] = 0;
    ind[0] = int(pt.size()) - 1; ind[1] = int(pt.size()) - 2; 
    for(int i = m - 1; i >= 0; i--){
        add_seg(i);
        while(ind[1] >= 0 && ans[0] >= ans[1]){
            ind[0] = ind[1];
            sumrbef[0] = sumrbef[1];
            cntbef[0] = cntbef[1];
            sumlaf[0] = sumlaf[1];
            cntaf[0] = cntaf[1];
            ans[0] = ans[1];
            dec();
        }
        suf[i] = ans[0];
        //cout << "suff " << i << ' ' << ind[0] << ' ' << ind[1] << ' '<< ans[0] << ' ' << ans[1] << endl;

    }

    ll ans = min(pref[m - 1], suf[0]);

    for(int i = 0; i < m - 1; i++)
        ans = min(ans, pref[i] + suf[i + 1]);

    cout << ans * 2 + all << endl;
}

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


2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

*/

Compilation message (stderr)

bridge.cpp: In function 'void add_seg(int)':
bridge.cpp:28:57: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int t = 0; t < 2; t++) if(ind[t] >= 0 && ind[t] < pt.size()){
      |                                                  ~~~~~~~^~~~~~~~~~~
bridge.cpp: In function 'void inc()':
bridge.cpp:46:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     if(ind[1] == pt.size())
      |        ~~~~~~~^~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:123:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         while(ind[1] < pt.size() && ans[0] > ans[1]){
      |               ~~~~~~~^~~~~~~~~~~
bridge.cpp:141:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |     for(int i = 0; i < pt.size(); i++){
      |                    ~~^~~~~~~~~~~

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