제출 #585985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585985		joig35	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	368 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;

/**
 * Author: Simon Lindholm
 * Date: 2015-09-12
 * License: CC0
 * Source: me
 * Description: When you need to dynamically allocate many objects and don't care about freeing them.
 * "new X" otherwise has an overhead of something like 0.05us + 16 bytes per allocation.
 * Status: tested
 */
#pragma once

// Either globally or in a single class:
static char buf[450 << 20];
void* operator new(size_t s) {
	static size_t i = sizeof buf;
	assert(s < i);
	return (void*)&buf[i -= s];
}
void operator delete(void*) {}
     
    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 = 1e6;
    const ll inf = 1e9 + 1;
    ll k, n;
    ll suf[maxN], pre[maxN];
     
    struct TNode{
        TNode *l, *r;
        ll 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[maxN];
     
    void create_node(TNode* id){
        if (!id->l) id->l = new TNode(0ll, 0ll);
        if (!id->r) id->r = new TNode(0ll, 0ll);
    }
     
    TNode* update(TNode* id, ll i, ll l = 0, ll r = inf){
        if (l == r) return new TNode(id->val + 1, id->sum + i);
        ll m = (l + r) / 2;
        create_node(id);
        if (m >= i) return new TNode(update(id->l, i, l, m), id->r);
        return new TNode(id->l, update(id->r, i, m + 1, r));
    }
     
    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(0ll, 0ll);
        for (ll i = 1; i <= v.size(); ++i){
            pre[i] = pre[i - 1] + v[i - 1].fi + v[i - 1].se;
            root[i] = update(root[i - 1], v[i - 1].fi);
            root[i] = update(root[i], v[i - 1].se);
        }
        ll tem = LLONG_MAX;
        for (ll i = 0; i < v.size() - 1; ++i){
            ll x = get(root[0], root[i + 1], i + 1);
            ll l = getsum(root[0], root[i + 1], 0, x) - remainer;
            ll y = get(root[i + 1], root[v.size()], v.size() - i - 1);
            ll r = getsum(root[i + 1], root[v.size()], 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();
    }

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp:18:9: warning: #pragma once in main file
   18 | #pragma once
      |         ^~~~
bridge.cpp: In function 'void Init()':
bridge.cpp:162:26: 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]
  162 |         for (ll i = 1; i <= v.size(); ++i){
      |                        ~~^~~~~~~~~~~
bridge.cpp:168:26: 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]
  168 |         for (ll i = 0; i < v.size() - 1; ++i){
      |                        ~~^~~~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:180:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |             freopen(taskname".txt", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:181:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |             freopen(taskname".out", "w", stdout);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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