Submission #39939

#	Time	Username	Problem	Language	Result	Execution time	Memory
39939		imaxblue	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	371 ms	8588 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()

int k, n, x[100005], y[100005], t, c1, c2, p=0, d;
ll ans, curr=0, ans2;
char ch, ch2;
vector<int> v;
multiset<pii> M1, R1, L2, M2, R2;
int32_t main(){
    cin >> k >> n;
    fox(l, n){
        cin >> ch >> x[d] >> ch2 >> y[d];
        if (x[d]>y[d]){t=x[d]; x[d]=y[d]; y[d]=t;}
        ans+=y[d]-x[d];
        if (ch!=ch2){
            v.pb(x[d]);
            v.pb(y[d]);
            curr+=x[d];
            --c2;
            ans++;
            R2.insert(mp(x[d], y[d]));
            ++d;
        }
    }
    //cout << d << endl;
    if (n<=100 && k==2){
        ans2=(1LL << 60);
        if (v.size()==0) ans2=0;
        fox(l, v.size()){
            for(int l2=l; l2<v.size(); ++l2){
                curr=0;
                fox(l3, d){
                    curr+=max(0, min(max(v[l]-y[l3], x[l3]-v[l]), max(v[l2]-y[l3], x[l3]-v[l2])));
                }
                ans2=min(ans2, curr);
            }
        }
        cout << ans+ans2*2;
        return 0;
    }
    ans2=curr;
    v.pb(0);
    sort(v.begin(), v.end());
    fox1(l, v.size()-1){
        curr+=1LL*c2*(v[l]-v[l-1]);
        //cout << v[l] << ' ' << curr << endl;
        while(R2.size() && R2.begin()->x<=v[l]){
            M2.insert(mp(R2.begin()->y, R2.begin()->x));
            R2.erase(R2.begin());
            ++c2;
        }
        while(M2.size() && M2.begin()->x<=v[l]){
            ++c2;
            L2.insert(mp(M2.begin()->y+M2.begin()->x, M2.begin()->y));
            M2.erase(M2.begin());
        }
        if (k==1){
            ans2=min(ans2, curr);
            continue;
        }
        while(L2.size() && v[p]>=L2.begin()->x-v[l]){
            --c1; --c2;
            if (!(v[p]>=L2.begin()->y))
                curr+=L2.begin()->x-v[l]-v[p];
            R1.insert(mp(L2.begin()->y, L2.begin()->x-L2.begin()->y));
            L2.erase(L2.begin());
        }
        while(R1.size() && R1.begin()->x<=v[p]){
            M1.insert(mp(R1.begin()->y, R1.begin()->x));
            R1.erase(R1.begin());
            ++c1;
        }
        while(M1.size() && M1.begin()->x<=v[p]){
            ++c1;
            M1.erase(M1.begin());
        }
        while(c1<=0 && p<l-1){
            curr+=1LL*(v[p+1]-v[p])*c1; ++p;
            while(L2.size() && v[p]>=L2.begin()->x-v[l]){
                --c1; --c2;
                if (!(v[p]>=L2.begin()->y))
                    curr+=L2.begin()->x-v[l]-v[p];
                R1.insert(mp(L2.begin()->y, L2.begin()->x-L2.begin()->y));
                L2.erase(L2.begin());
            }
            while(R1.size() && R1.begin()->x<=v[p]){
                M1.insert(mp(R1.begin()->y, R1.begin()->x));
                R1.erase(R1.begin());
                ++c1;
            }
            while(M1.size() && M1.begin()->x<=v[p]){
                ++c1;
                M1.erase(M1.begin());
            }
        }
        /*if (curr<ans2){
            cout << v[p] << ' '  << v[l] << ' ' << c1 << ' ' << c2 << ' ' << curr << endl;
        }*/
        ans2=min(ans2, curr);
    }
    //cout << ans << ' ' << ans2 << endl;
    cout << ans+ans2*2;
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int32_t main()':
bridge.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
bridge.cpp:52:9: note: in expansion of macro 'fox'
         fox(l, v.size()){
         ^
bridge.cpp:53:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int l2=l; l2<v.size(); ++l2){
                             ^
bridge.cpp:19:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox1(k, x) for (int k=1; k<=x; ++k)
                                   ^
bridge.cpp:67:5: note: in expansion of macro 'fox1'
     fox1(l, v.size()-1){
     ^

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