Submission #615363

#	Time	Username	Problem	Language	Result	Execution time	Memory
615363		Do_you_copy	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	559 ms	262144 KiB

bridge

#include <bits/stdc++.h>
#define taskname "test"
#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 pii = pair <ll, ll>;

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 maxN = 3e5;
const ll inf = 1e9 + 1;
ll k, n;
ll suf[maxN], pre[maxN];

ll cnt = 0;

struct __attribute__((packed)) TNode{
    TNode *l, *r;
    int val;
    ll sum;
    TNode (const ll &i, const ll &j) : l(nullptr), r(nullptr), val(i), sum(j){}
    TNode (TNode* i, TNode* j){
        l = i; r = j;
        val = 0; sum = 0;
        if (l){
            val += l->val;
            sum += l->sum;
        }
        if (r){
            val += r->val;
            sum += r->sum;
        }
    }
};

TNode* root[3];


void create_node(TNode* id){
    if (!id->l){
        ++cnt;
        id->l = new TNode(0, 0ll);
    }
    if (!id->r){
        ++cnt;
        id->r = new TNode(0, 0ll);
    }
}

void update(TNode* id, ll i, ll l = 0, ll r = inf){
    if (l == r){
        ++id->val; id->sum += i;
        return;
    };
    ll m = (l + r) / 2;
    create_node(id);
    if (m >= i) update(id->l, i, l, m);
    else update(id->r, i, m + 1, r);
    id->sum = id->l->sum + id->r->sum;
    id->val = id->l->val + id->r->val;
}
ll remainer;

ll get(TNode* left, TNode* right, ll k, ll l = 0, ll r = inf){
    //finding the kth largest numbers from left -> right
    if (l == r){
        remainer = right->sum - left->sum - (l * k);
        return l;
    }
    ll m = (l + r) / 2;
    ll cntl = (left->l) ? left->l->val : 0;
    ll cntr = (right->l) ? right->l->val : 0;
    if (cntr - cntl < k) return get((left->r) ? left->r : left, (right->r) ? right->r : right, k - cntr + cntl, m + 1, r);
    return get((left->l) ? left->l : left, (right->l) ? right->l : right, k, l, m);
}

ll getsum(TNode* left, TNode* right, ll i, ll j, ll l = 0, ll r = inf){
    //get sum of all elements ranged between i and j from left to right
    if (r < i || l > j) return 0;
    if (i <= l && r <= j){
        return right->sum - left->sum;
    }
    ll m = (l + r) / 2;
    ll x = getsum((left->l) ? left->l : left, (right->l) ? right->l : right, i, j, l, m);
    ll y = getsum((left->r) ? left->r : left, (right->r) ? right->r : right, i, j, m + 1, r);
    return x + y;
}

void Init(){
    ll ans = 0;
    cin >> k >> n;
    if (k == 1){
        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;
    }
    vector <pii> 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, t});
        }
        else ans += abs(s - t);
    }
    if (v.empty()){
        cout << ans; return;
    }
    if (v.size() == 1){
        cout << ans + abs(v[0].fi - v[0].se);
        return;
    }
    sort(v.begin(), v.end(),[](const pii &i, const pii &j){
        return (i.fi + i.se) / 2 < (j.fi + j.se) / 2;
    });
    root[0] = new TNode(0, 0ll);
    root[1] = new TNode(0, 0ll);
    root[2] = new TNode(0, 0ll);
    for (ll i = 1; i <= v.size(); ++i){
        pre[i] = pre[i - 1] + v[i - 1].fi + v[i - 1].se;
        update(root[2], v[i - 1].fi);
        update(root[2], v[i - 1].se);
    }
    ll tem = LLONG_MAX;
    for (ll i = 0; i < v.size() - 1; ++i){
        update(root[1], v[i].fi);
        update(root[1], v[i].se);
        ll x = get(root[0], root[1], i + 1);
        ll l = getsum(root[0], root[1], 0, x) - remainer;
        ll y = get(root[1], root[2], v.size() - i - 1);
        ll r = getsum(root[1], root[2], 0, y) - remainer;
        tem = min(tem, pre[i + 1] - 2 * l + pre[v.size()] - pre[i + 1] - 2 * r);
    }
    cout << tem + ans;
}

signed main(){
    if (fopen(taskname".txt", "r")){
        freopen(taskname".txt", "r", stdin);
        //freopen(taskname".out", "w", stdout);
    }
    faster
    Init();
}

Compilation message (stderr)

bridge.cpp: In function 'void Init()':
bridge.cpp:157:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for (ll i = 1; i <= v.size(); ++i){
      |                    ~~^~~~~~~~~~~
bridge.cpp:163:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for (ll i = 0; i < v.size() - 1; ++i){
      |                    ~~^~~~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:177:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |         freopen(taskname".txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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