Submission #978360

#	Time	Username	Problem	Language	Result	Execution time	Memory
978360		nnin	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	114 ms	14400 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
using ll = long long;
#define f first
#define s second

vector<int> en, st;
int N, K;
ll sum1[100005], sum2[100005];
set<int> posi;

ll one() {
    if(st.empty()) return 0;
    for(int i=0;i<en.size();i++) sum1[i+1] = sum1[i]+en[i];
    for(int i=st.size()-1;i>=0;i--) sum2[i+1] = sum2[i+2]+st[i];
    ll ret = 1e18;
    for(int p:posi) {
        int bef = lower_bound(en.begin(), en.end(), p)-en.begin()-1;
        int aft = upper_bound(st.begin(), st.end(), p)-st.begin();
        ret = min(ret, ((ll)(bef+1)*(ll)p)-sum1[bef+1]+sum2[aft+1]-(((ll)st.size()-aft)*(ll)p));
    }
    return 2*ret;
}

ll two() {
    if(st.empty()) return 0;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>K>>N;
    ll ans = 0;
    for(int i=0;i<N;i++) {
        char z1, z2;
        int b1, b2;
        cin>>z1>>b1>>z2>>b2;
        ans += abs(b1-b2);
        if(z1!=z2) {
            ans++;
            st.push_back(min(b1, b2));
            en.push_back(max(b1, b2));
            posi.insert(b1);
            posi.insert(b2);
        }
    }
    sort(st.begin(), st.end());
    sort(en.begin(), en.end());
    if(K==1) cout<<ans+one();
    else cout<<ans+two();
}

Compilation message (stderr)

bridge.cpp: In function 'll one()':
bridge.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i=0;i<en.size();i++) sum1[i+1] = sum1[i]+en[i];
      |                 ~^~~~~~~~~~
bridge.cpp: In function 'll two()':
bridge.cpp:28:1: warning: control reaches end of non-void function [-Wreturn-type]
   28 | }
      | ^

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