제출 #937549

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
937549		VinhLuu	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	79 ms	17328 KiB

bridge

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 2e5 + 5;
const ll oo = 1e18;
const int mod = 1e9 + 7;
const int K = 1e5 + 5;

char P[N], Q[N];
int S[N], T[N], k, n;
ll ans, s[N];
vector<ll> vr;
vector<pii> h;
int cnt = 0;

namespace sub1{
    void solve(){
        ll ret = oo;
        for(int i = 1; i <= cnt << 1; i ++){
            for(int j = i + 1; j <= cnt << 1; j ++){
                ll kq = 0;
                if(vr[i - 1] == 36 && vr[j - 1] == 91){
                for(auto [l, r] : h){
                    if(l <= vr[i - 1] && vr[i - 1] <= r){
                        cout << l << " " << r << " 1\n";
                        kq += 1 + vr[i - 1] - l + r - vr[i - 1];
                    }
                    else if(l <= vr[j - 1] && vr[j - 1] <= r){
                        kq += 1 + vr[j - 1] - l + r - vr[j - 1];
                        cout << l << " " << r << " 2\n";
                    }
                    else if(vr[i - 1] <= l && r <= vr[j - 1]){
                        kq += 1 + min(l - vr[i - 1] + r - vr[i - 1], vr[j - 1] - l + vr[j - 1] - r);
                        cout << l << " " << r << " 1\n";
                    }
                    else if(r <= vr[i - 1]){
                        cout << l << " " << r << " 1\n";
                        kq += 1 + vr[i - 1] - l + vr[i - 1] - r;
                    }
                    else{
                        kq += 1 + l - vr[j - 1] + r - vr[j - 1];
                        cout << l << " " << r << " 2\n";
                    }
                }
//                if(kq + ans == 150) cout << vr[i - 1] << " " << vr[j - 1] << "f\n";
                ret = min(ret, kq + ans);return;}
            }
        }
        ans = ret;
    }
}

namespace sub3{
    int pre[N], sf[N], a[N];

    int le, ri;

    priority_queue<int,vector<int>,greater<int>> mi;
    priority_queue<int> mx;

    void add(int x){
        if(x >= mi.top()){
            if((int)mx.size() <= mi.size()){
                mx.push(mi.top());
                le += mi.top();
                ri -= mi.top();
                mi.pop();
            }
            mi.push(x);
            ri += x;
        }else if(x <= mx.top()){
            if((int)mx.size() > (int)mi.size()){
                mi.push(mx.top());
                ri += mx.top();
                le -= mx.top();
                mx.pop();
            }
            le += x;
            mx.push(x);
        }else{
            if((int)mx.size() <= (int)mi.size()){
                le += x;
                mx.push(x);
            }else{
                mi.push(x);
                ri += x;
            }
        }
    }

    void solve(){
//        for(auto j : h) cout << j.fi << " " << j.se << "g\n";
        ans += cnt;
//        cout << ans << "h\n";
        cnt = 0;
        sort(all(h), [] (pii x, pii y){return x.fi + x.se < y.fi + y.se;});
        cnt = h.size();
//        for(auto j : h) cout << j.fi << " " << j.se << "r\n";

        pre[1] = h[0].se - h[0].fi;
        mi.push(h[0].se);
        mx.push(h[0].fi);
        ri = h[0].se;
        le = h[0].fi;

        for(int i = 2; i <= cnt; i ++){
            add(h[i - 1].fi);
            add(h[i - 1].se);
            pre[i] = ri - le;
        }

        while(!mx.empty()) mx.pop();
        while(!mi.empty()) mi.pop();

        sf[cnt] = h[cnt - 1].se - h[cnt - 1].fi;
        mi.push(h[cnt - 1].se);
        mx.push(h[cnt - 1].fi);
        le = h[cnt - 1].fi;
        ri = h[cnt - 1].se;
        for(int i = cnt - 1; i >= 1; i --){
            add(h[i - 1].fi);
            add(h[i - 1].se);
            sf[i] = ri - le;
        }

//        for(int i = 1; i <= cnt; i ++) cout << i << " " << pre[i] << " " << sf[i] << "uuuu\n";

        int ret = oo;

        for(int i = 1; i <= cnt; i ++){
//            cout << i << " " << pre[i] << " " << sf[i + 1] << "f\n";
            ret = min(ret, pre[i] + sf[i + 1]);
        }
//        cout << ans << "u\n";
        ans += ret;
    }
}

namespace sub2{
    ll cal(int i,int j){
        ll kq = 0;
        for(auto [l, r] : h){
            if(l <= i && i <= r) kq += 1 + i - l + r - i;
            else if(l <= j && j <= r) kq += 1 + j - l + r - j;
            else if(i <= l && r <= j) kq += 1 + min(l - i + r - i, j - l + j - r);
            else if(r <= i) kq += 1 + i - l + i - r;
            else kq += 1 + l - j + r - j;
        }
        return kq;
    }
    void solve(){
        ll ret = oo;

        for(int i = 1; i <= cnt * 2; i ++){
            int l = vr[i - 1] + 1;
            int r = min((int)1e9, vr[cnt * 2 - 1] + 1);
            while(l < r - 2){
                int m1 = l + (r - l)/3, m2 = r - (r - l)/3;
                ll u = cal(vr[i - 1], m1);
                ll v = cal(vr[i - 1], m2);
//                if(u == 27) cout << i << " "<< m1 << "g\n";
//                if(v == 27) cout << i << " " << m2<< "g\n";
                if(u > v) l = m1; else r = m2;
                ret = min({ret, u, v});
            }
            for(int j = l; j <= r; j ++) ret = min(ret, cal(vr[i - 1], j));
//            cerr << i << " " << ret << "f\n";
        }
        ans = ret + ans;
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    cin >> k >> n;


    for(int i = 1; i <= n; i ++){
        cin >> P[i] >> S[i] >> Q[i] >> T[i];
        if(P[i] == Q[i]){
            ans += abs(S[i] - T[i]);
            continue;
        }
        vr.pb(S[i]);
        vr.pb(T[i]);
        cnt++;
        if(S[i] > T[i]) swap(S[i], T[i]);
        h.pb({S[i], T[i]});
    }
    if(!vr.empty()){
        sort(vr.begin(), vr.end());
        for(int i = 1; i <= cnt * 2; i ++) s[i] = s[i - 1] + vr[i - 1];
        if(k == 1){
            ll kq = oo;
            ll lim = vr[cnt - 1];
            for(int j = max(vr[0], lim - (ll)0); j <= min(vr[2 * cnt - 1], lim + (ll)0); j ++){
                int i = lower_bound(all(vr), j) - vr.begin();
                if(i < 2 * cnt){
                    i++;
                }
                    kq = min(kq, cnt + 1ll * j * (i - 1) - 1ll * j * (1ll * 2 * cnt - i + 1) - s[i - 1] + s[cnt * 2] - s[i - 1]);
            }
            ans = ans + kq;
        }else{
//            if(n <= 100)
//                sub1 :: solve();

//            else
//            if(n <= 1000)
//                sub2 :: solve();
//            else
                sub3 :: solve();
        }
    }
    cout << ans;

}

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

bridge.cpp: In function 'void sub3::add(long long int)':
bridge.cpp:76:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             if((int)mx.size() <= mi.size()){
      |                ~~~~~~~~~~~~~~~^~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:191:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:192:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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