제출 #979869

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
979869		ByeWorld	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	1408 ms	19276 KiB

bridge

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const int MAXN = 2e5+10;
const int INF = 4e18+10;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
 
int K, n, MX;
int ans, MN = INF;
vector <pii> cc;
vector <int> v;
 
int cek(int idx){
    /*int res = INF;
    for (int x : v) {
        if (x == idx) break;
        int t = 0, a, b;
        for (auto in : cc) {
            a = abs(in.fi - idx) + abs(in.se - idx);
            b = abs(in.fi - x) + abs(in.se - x);
            t += min(a,b);
        }
        res = min(res,t);
    }
    return res;*/
    
    int ret = 0, m = 0, c = 0;
    int mn = 0;
    vector <pii> vec;
    for(auto in : cc){
        if(in.fi <= idx && idx <= in.se){
            ret += in.se-in.fi;
        } else if(idx<=in.fi && idx<=in.se){
            ret += in.se-idx+in.fi-idx;
        } else {
            int a = in.fi, b = in.se;
            vec.pb({a+b-idx, 0});
            vec.pb({a, 1});
            vec.pb({b, 1});
            c += 2*idx-a-b;
        }
    }
    mn = c;
    sort(vec.begin(), vec.end());
    
    for(int i=0; i<vec.size(); i++){
        int nw = vec[i].fi;
        /*while(i+1<vec.size() && vec[i+1].fi == vec[i].fi){
            // upd i
            if(vec[i].se){
                m += 2;
                c += -2*nw;
            } else {
                m -= 2;
                c += 2*nw;
            }
            i++;
        }*/
        // upd i
        if(vec[i].se){
            m += 2;
            c += -2*nw;
        } else {
            m -= 2;
            c += 2*nw;
        }
        
        mn = min(mn, m*nw+c);
    }
    return ret+mn;
    
    // <a[i]+b[i]-idx,<-2,2*a[i]+2*b[i]-2*idx>>
    // <a[i],<2,-2*a[i]>>
    // <b[i],<2,-2*b[i]>>
    
    // <a[i]+b[i]-idx,0>
    // <a[i],1>
    // <b[i],1>
    
    // idx-b[i] <= a[i]-x
    // x <= a[i]+b[i]-idx
    // 2*idx-a[i]-b[i]
    
    // a[i]+b[i]-idx <= x <= a[i]
    // a[i]+b[i]-2x
    
    // a[i] <= x <= b[i]
    // b[i]-a[i]
    
    // b[i] <= x
    // 2x-a[i]-b[i]
    
    // <a[i],i>
    // <b[i],i>
}
void solve(){
	cin >> K >> n;
    if(K==1){
        vector <int> vec;
		vec.pb(-1);
		for(int i=1; i<=n; i++){
			char x, y; int a, b;
			cin >> x >> a >> y >> b; a++; b++;
			if(x==y) ans += abs(a-b);
			else {
				vec.pb(a); vec.pb(b);
			}
		}
		sort(vec.begin(), vec.end()); 
 
		int MN = INF, siz = vec.size()-1;
		for(int i=1; i<=siz; i++){
			ans += abs(vec[(siz+1)/2]-vec[i]);
		}
		ans += siz/2;
		cout << ans << '\n';
        exit(0);
	}
    
    v.pb(-1);
    for(int i=1; i<=n; i++){
        char x, y; int a, b;
        cin >> x >> a >> y >> b; a++; b++;
        if(x==y){
            ans += abs(a-b); continue;
        }
        if(a > b) swap(a, b);
        cc.pb({a, b});
        v.pb(a); v.pb(b);
    }
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    
    
    int l=1, r=v.size()-1, mid1=0, mid2=0;
    while(r-l+1 >= 40){
        mid1 = (l+l+r)/3; mid2 = (l+r+r+2)/3;
        int num1 = cek(v[mid1]), num2 = cek(v[mid2]);
        // cout << mid1 << " " << mid2 << " " << cek(mid1) << " " << cek(mid2) << endl;
        MN = min(MN, min(num1, num2));
        if(num1 < num2) r = mid2;
        else l = mid1;
    }
    // cout << l << ' ' << r << " lr\n";
    for(int mid=l; mid<=r; mid++){
        // cout << mid << " " << cek(mid) << endl;
        MN = min(MN, cek(v[mid]));
    }
    if(cc.size() == 0) MN = 0;
    cout << ans + MN + (int)cc.size() << '\n';
    
    ans = 0; MN = INF;
    cc.clear(); v.clear();
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // int T = 1;
    // while(T--){
    //     solve();
    // }
    solve();
}

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

bridge.cpp: In function 'long long int cek(long long int)':
bridge.cpp:51:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i=0; i<vec.size(); i++){
      |                  ~^~~~~~~~~~~
bridge.cpp: In function 'void solve()':
bridge.cpp:116:7: warning: unused variable 'MN' [-Wunused-variable]
  116 |   int MN = INF, siz = vec.size()-1;
      |       ^~

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