Submission #635542

#	Time	Username	Problem	Language	Result	Execution time	Memory
635542		Do_you_copy	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	80 ms	81880 KiB

bridge

#include <bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 3e5 + 1;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, k;

vector <int> val[maxN * 4];
vector <ll> sum[maxN * 4];
vector <int> b;
ll pre[maxN], suf[maxN];
int wt_sz = 1;
struct TNode{
    int l, r;
    int lp, rp;
    TNode(){
        l = r = lp = rp = 0;
    }
    TNode(int _l, int _r) : l(_l), r(_r){};
};
TNode wt[maxN * 4];

void build(int id, auto i, auto j, int l, int r){
    wt[id].l = l;
    wt[id].r = r;
    if (l == r){
        return;
    }
    val[id].pb(0);
    sum[id].pb(0);
    int mid = (l + r) / 2;
    int maxx = l, minn = r;
    for (auto it = i; it != j; ++it){
        bool t = *it <= mid;
        val[id].pb(val[id].back() + t);
        sum[id].pb(sum[id].back() + *it * t);
        if (t) maxx = max(maxx, *it);
        else minn = min(minn, *it);
    }
    auto p = stable_partition(i, j,[=](const auto &w){
        return w <= mid;
    });
    wt[id].lp = ++wt_sz;
    wt[id].rp = ++wt_sz;
    build(wt[id].lp, i, p, l, maxx);
    build(wt[id].rp, p, j, minn, r);
}

ll get(int k, int i, int j){
    if (k == 0) return 0;
    --i;
    ll res = 0;
    int id = 1;
    int l = wt[id].l, r = wt[id].r;
    while (l < r){
        int mid = (l + r) / 2;
        if (k <= val[id][j] - val[id][i]){
            i = val[id][i];
            j = val[id][j];
            id = wt[id].lp;
        }
        else{
            res += sum[id][j] - sum[id][i];
            k -= val[id][j] - val[id][i];
            i -= val[id][i];
            j -= val[id][j];
            id = wt[id].rp;
        }
        l = wt[id].l, r = wt[id].r;
    }
    res += k * l;
    return res;
}

void Init(){
    cin >> k >> n;
    if (k == 1){
        ll ans = 0;
        vector <ll> v;
        for (ll i = 1; i <= n; ++i){
            char p, q; ll s, t;
            cin >> p >> s >> q >> t;
            if (p != q){
                ++ans;
                v.pb(s);
                v.pb(t);
            }
            else{
                ans += abs(s - t);
            }
        }
        v.push_back(0);
        sort(v.begin(), v.end());
        ll m = v.size();
        ll tem = LLONG_MAX;
        for (ll i = 1; i < m; ++i){
            pre[i] = pre[i - 1] + v[i];
        }
        for (ll i = m - 1; i > 0; --i){
            suf[i] = suf[i + 1] + v[i];
        }
        for (ll i = 1; i < m; ++i){
            tem = min(tem, v[i] * (i - 1) - pre[i - 1] + suf[i + 1] - v[i] * (m - i - 1));
        }
        if (m == 1) tem = 0;
        cout << ans + tem;
        return;
    }
    ll ans = 0;
    vector <pii> v;
    for (int i = 1; i <= n; ++i){
        char p, q; int s, t;
        cin >> p >> s >> q >> t;
        if (p == q) ans += abs(s - t);
        else{
            ++ans; //cost to go through a bridge
            v.pb({s, t});
        }
    }
    sort(v.begin(), v.end(),[](const auto &i, const auto &j){
        return (i.fi + i.se) / 2 < (j.fi + j.se) / 2;
    });
    if (v.empty()){
        cout << ans; return;
    }
    if (v.size() == 1){
        cout << ans + abs(v[0].fi - v[0].se); return;
    }
    ll tem = inf;
    b.resize(2 * v.size() + 1);
    for (int i = 1; i <= v.size(); ++i){
        pre[i] = pre[i - 1] + v[i - 1].fi + v[i - 1].se;
    }
    for (int i = 0; i < v.size(); ++i){
        b[i * 2 + 1] = v[i].fi;
        b[i * 2 + 2] = v[i].se;
    }
    build(1, b.begin() + 1, b.end(), *min_element(b.begin(), b.end()), *max_element(b.begin(), b.end()));
    for (int i = 0; i < v.size() - 1; ++i){
        ll l = get(i + 1, 1, i * 2 + 2);
        ll r = get(v.size() - i - 1, i * 2 + 3, v.size() * 2);
        tem = min(tem, pre[i + 1] - 2 * l + pre[v.size()] - pre[i + 1] - 2 * r);
    }
    cout << tem + ans;
}

#define debu
#define taskname "test"
signed main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        #ifdef debug
        freopen(taskname".out", "w", stdout);
        #endif
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        timeout << 1000 * double(clock()) / CLOCKS_PER_SEC;
        #ifndef debug
        cerr << "\nTime elapsed: " << 1000 * double(clock()) / CLOCKS_PER_SEC << "ms\n";
        #endif
    }
}

Compilation message (stderr)

bridge.cpp:47:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   47 | void build(int id, auto i, auto j, int l, int r){
      |                    ^~~~
bridge.cpp:47:28: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   47 | void build(int id, auto i, auto j, int l, int r){
      |                            ^~~~
bridge.cpp: In function 'll get(int, int, int)':
bridge.cpp:80:13: warning: unused variable 'mid' [-Wunused-variable]
   80 |         int mid = (l + r) / 2;
      |             ^~~
bridge.cpp: In function 'void Init()':
bridge.cpp:155:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for (int i = 1; i <= v.size(); ++i){
      |                     ~~^~~~~~~~~~~
bridge.cpp:158:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     for (int i = 0; i < v.size(); ++i){
      |                     ~~^~~~~~~~~~
bridge.cpp:163:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for (int i = 0; i < v.size() - 1; ++i){
      |                     ~~^~~~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:175:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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