Submission #1150057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150057		imarn	Palembang Bridges (APIO15_bridge)	C++20	22 / 100	28 ms	5052 KiB

bridge

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
#define sz(x) (ll)x.size()
using namespace std;
const int mxn=1e5+5;
ll rs=0;
vector<pll>v;
void sol1(){
    vector<ll>vx;
    for(auto [x,y]:v)vx.pb(x),vx.pb(y);
    sort(all(vx));
    ll y=vx[vx.size()/2];
    for(auto it : vx)rs+=abs(it-y);
    cout<<rs;
}
bool cmp(pll a,pll b){
    return (a.f+b.f)<a.s+b.s;
}
void sol2(){
    int n=v.size();
    sort(all(v),cmp);
    ll dpl[n+2]={0},dpr[n+2]={0};
    priority_queue<ll>lq;
    priority_queue<ll,vector<ll>,greater<ll>>rq;
    ll sl=0,sr=0;
    for(int i=0;i<n;i++){
        lq.push(v[i].f);lq.push(v[i].s);sl+=v[i].f+v[i].s;
        while(!lq.empty()&&!rq.empty()&&lq.top()>rq.top())sl-=lq.top(),sr+=lq.top(),rq.push(lq.top()),lq.pop();
        while(!rq.empty()&&sz(rq)>=sz(lq)+1)sr-=rq.top(),sl+=rq.top(),lq.push(rq.top()),rq.pop();
        while(!lq.empty()&&sz(lq)>sz(rq)+1)sl-=lq.top(),sr+=lq.top(),rq.push(lq.top()),lq.pop();
        dpl[i+1]=sz(lq)*lq.top()-sl+sr-sz(rq)*lq.top();
    }while(!lq.empty())lq.pop();while(!rq.empty())rq.pop();sl=0,sr=0;
    for(int i=n-1;i>=0;i--){
        lq.push(v[i].f);lq.push(v[i].s);sl+=v[i].f+v[i].s;
        while(!lq.empty()&&!rq.empty()&&lq.top()>rq.top())sl-=lq.top(),sr+=lq.top(),rq.push(lq.top()),lq.pop();
        while(!rq.empty()&&sz(rq)>=sz(lq)+1)sr-=rq.top(),sl+=rq.top(),lq.push(rq.top()),rq.pop();
        while(!lq.empty()&&sz(lq)>sz(rq)+1)sl-=lq.top(),sr+=lq.top(),rq.push(lq.top()),lq.pop();
        dpr[i+1]=sz(lq)*lq.top()-sl+sr-sz(rq)*lq.top();
    }ll rs2=1e16;
    for(int i=0;i<=n;i++){
        rs2 = min(rs2,dpl[i]+dpr[i+1]);
    }cout<<rs+rs2;

}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int k,n;cin>>k>>n;
    for(int i=1;i<=n;i++){
        char x,y;ll xx,yy;
        cin>>x>>xx>>y>>yy;
        if(x==y)rs+=abs(yy-xx);
        else if(x=='A')v.pb({xx,yy}),rs++;
        else v.pb({yy,xx}),rs++;
    }
    if(k==1)sol1();
    if(k==2)sol2();
}

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