Submission #585506

#	Time	Username	Problem	Language	Result	Execution time	Memory
585506		karrigan	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	2 ms	468 KiB

bridge

#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);
using namespace std;
struct line{
char x,z;
long long y,t;
}a[100001];
vector<long long>b[2];
vector<long long>pf[2];
int main()
{
    fastio
    int k,n;
    cin>>k>>n;
    long long ans=0;
    for (int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y>>a[i].z>>a[i].t;
        if (a[i].x!=a[i].z){
            b[a[i].x-'A'].push_back(a[i].y);
            b[a[i].z-'A'].push_back(a[i].t);
        }
        else {
            ans+=abs(a[i].y-a[i].t);
        }
    }
    sort(b[0].begin(),b[0].end());
    sort(b[1].begin(),b[1].end());
    long long cal=1e16;
    for (int i=0;i<2;i++){
        pf[i].resize(b[i].size()+2);
        pf[i][0]=b[i][0];
        //for (auto v:b[i])cout<<v<<" ";
        //cout<<'\n';
        for (int j=1;j<(int)b[i].size();j++){
            pf[i][j]=pf[i][j-1]+b[i][j];
        }
    }
    for (int i=1;i<=1;i++){
        if (a[i].x!=a[i].z){
            int d=upper_bound(b[0].begin(),b[0].end(),a[i].y)-b[0].begin();
            int e=upper_bound(b[1].begin(),b[1].end(),a[i].y)-b[1].begin();
            long long l1,r1,l2,r2;
            if (d>0){
            l1=d*a[i].y-pf[0][d-1];
            r1=pf[0][(int)b[0].size()-1]-pf[0][d-1]-((int)b[0].size()-d)*a[i].y;
            }
            else {
            l1=0;
            r1=pf[0][(int)b[0].size()-1]-((int)b[0].size())*a[i].y;
            }
            if (e>0){
            l2=e*a[i].y-pf[1][e-1];
            r2=pf[1][(int)b[1].size()-1]-pf[1][e-1]-((int)b[1].size()-e)*a[i].y;
            }
            else {
            l2=0;
            r2=pf[1][(int)b[1].size()-1]-((int)b[1].size())*a[i].y;
            }
            //cout<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<'\n';
            cal=min(cal,l1+r1+l2+r2+ans+(long long)b[1].size());
            d=upper_bound(b[0].begin(),b[0].end(),a[i].t)-b[0].begin();
            e=upper_bound(b[1].begin(),b[1].end(),a[i].t)-b[1].begin();
            if (d>0){
            l1=d*a[i].t-pf[0][d-1];
            r1=pf[0][(int)b[0].size()-1]-pf[0][d-1]-((int)b[0].size()-d)*a[i].t;
            }
            else {
            l1=0;
            r1=pf[0][(int)b[0].size()-1]-((int)b[0].size())*a[i].t;
            }
            if (e>0){
            l2=e*a[i].t-pf[1][e-1];
            r2=pf[1][(int)b[1].size()-1]-pf[1][e-1]-((int)b[1].size()-e)*a[i].t;
            }
            else {
            l2=0;
            r2=pf[1][(int)b[1].size()-1]-((int)b[1].size())*a[i].t;
            }
            //cout<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<'\n';
            cal=min(cal,l1+r1+l2+r2+(long long)b[1].size()+ans);
            //cout<<e<<" "<<l2<<" "<<r2<<'\n';
        }
    }
    cout<<cal;
    /*
    1 5
    B 0 A 4
    B 1 B 3
    A 5 B 7
    B 2 A 6
    B 1 A 7
    */
}

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