Submission #540312

#	Time	Username	Problem	Language	Result	Execution time	Memory
540312		jli12345	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	2076 ms	5380 KiB

bridge

#pragma GCC optimize("Ofast,fast-math,unroll-loops")
#include <iostream>
#include <queue>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;

void fastIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

typedef long long ll;
typedef pair<int, int> pii;
#define ff first
#define ss second

int K, N, A[100100], B[100100], cnt = 0;
ll same = 0;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int comb[200100];

ll solve1(){
    for (int i = 1; i <= cnt; i++){
        comb[2*i-1] = A[i];
        comb[2*i] = B[i];
    }
    sort(comb+1, comb+2*cnt+1);
    int mid = comb[cnt];
    ll ans = same+cnt;
    for (int i = 1; i <= cnt; i++){
        ans += abs(A[i]-mid)+abs(B[i]-mid);
    }
    return ans;
}

pii comb2[200100];
pii loc[200100];

pii v[200100];

void solve2(){
    for (int i = 1; i <= cnt; i++){
        comb2[2*i-1] = {A[i], i};
        comb2[2*i] = {B[i], i};
    }
    sort(comb2+1, comb2+1+2*cnt);
    for (int i = 1; i <= 2*cnt; i++){
        if (loc[comb2[i].ss].ff == 0){
            loc[comb2[i].ss].ff = i;
        } else {
            loc[comb2[i].ss].ss = i;
        }
    }
    int bl = 0, br = 0, bml = 0;//bl is both left, br is both right, bml is middle but goes to left bridge
    set<pair<int, int> > s; //sum index

    int r = 2;
    ll cur = 0, best = LINF;
    for (int i = 1; i <= cnt; i++){
        if (loc[i].ff > 2 && loc[i].ss > 2) br++;
        cur += abs(A[i]-comb2[2].ff)+abs(B[i]-comb2[2].ff);
    }
    best = cur;
    //cout << "bl br bml size cur\n";
    for (int i = 1; i <= 2*cnt-2; i++){//i represents the left pointer
        //cout << i << ":\n";
        int lpos = comb2[i].ff;
        ll pre = cur;
        bool stop = false;
        while (r < 2*cnt){
            //deal with br
            ll ncur = cur;
            ncur -= (ll)2*br*(comb2[r+1].ff-comb2[r].ff);
            

            //deal with set
            int numerase = 0;
            //vector<pair<int, int> > v;
            int vind = 1;
            for (pair<int, int> x : s){
                int distl = x.ff-2*lpos;
                int distr = 2*(comb2[r].ff-lpos)-distl;
                int distnr = 2*(comb2[r+1].ff-lpos)-distl;
                if (distnr >= distl){
                    ncur += distl-distr;
                    numerase++;
                    //v.push_back(x);
                    v[vind++] = x;
                } else {
                    break;
                }
            }
            for (int x = 1; x <= numerase; x++) s.erase(s.begin());
            ncur += (ll)2*(int)s.size()*(comb2[r+1].ff-comb2[r].ff);

            if (ncur > pre || stop){
                if (r > i+1){
                    //revert
                    for (int k = 1; k < vind; k++) s.insert(v[k]);
                    break;
                } else {
                    stop = true;
                }
            }
            cur = ncur;
            if (loc[comb2[r+1].ss].ff == r+1){
                br--;
            }
            if (loc[comb2[r+1].ss].ss == r+1){
                if (loc[comb2[r+1].ss].ff > i){
                    int ind = comb2[r+1].ss;
                    int distl = A[ind]+B[ind]-2*lpos;
                    int distr = 2*(comb2[r+1].ff-lpos)-distl;
                    if (distr < distl)
                        s.insert(make_pair(A[ind]+B[ind], ind));
                    else
                        bml++;
                }
            }
            //deal with bml
            bml += numerase;
            r++;
            best = min(best, cur);
            //cout << bl << " " << br << " " << bml << " " << (int)s.size() << " " << cur << "\n";
            pre = cur;
        }
        /*cout << bl << " " << (int)s.size() << " " << bml << "\n";
        for (pii x : s) cout << x.ff << " " << x.ss << "\n";
        cout << "\n";*/
        //now increment the l pointer

        //deal with bl
        cur += (ll)2*bl*(comb2[i+1].ff-comb2[i].ff);
        if (loc[comb2[i+1].ss].ss == i+1){
            bl++;
        }
        //deal with set
        cur -= (ll)2*bml*(comb2[i+1].ff-comb2[i].ff);
        //first erase
        if (loc[comb2[i+1].ss].ff == i+1){
            if (loc[comb2[i+1].ss].ss <= r){
                //cout << "HElo\n";
                int ind = comb2[i+1].ss;
                int distl = A[ind]+B[ind]-2*lpos;
                int distnl = A[ind]+B[ind]-2*comb2[i+1].ff;
                int distr = 2*(comb2[r].ff-comb2[i].ff)-distl;
                //cout << A[ind] << " " << B[ind] << "\n";
                //cout << distl << " " << distr << "\n";
                if (distr < distl){
                    cur += distnl-distr;
                    s.erase({A[ind]+B[ind], ind});
                } else {
                    bml--;
                }
            }
        }

        int numerase = 0;
        int nlpos = comb2[i+1].ff;
        for (pair<int, int> x : s){
           // int distl = x.ff-2*lpos;
            int distnl = x.ff-2*nlpos;
            int distr = 2*(comb2[r].ff-nlpos)-distnl;
            if (distr >= distnl){
                cur += distnl-distr;
                numerase++;
            } else {
                break;
            }
        }
        for (int x = 1; x <= numerase; x++) s.erase(s.begin());
        bml += numerase;
        best = min(best, cur);
        //cout << "ed: " << r << " " << cur << "\n";
        //cout << "Ed: ";
        //cout << bl << " " << br << " " << bml << " " << (int)s.size() << " " << cur << "\n";
    }
    cout << best+same+cnt << "\n";
}

const int BUFSIZE=20<<20;//20MB
char Buf[BUFSIZE+1],*buf=Buf;
//fread(Buf,1,BUFSIZE,stdin); 在读入之前写这句话  任何整数
template<class T>
void scan(T&a){
    int sgn=1;
    for(a=0;*buf<'0'||*buf>'9';buf++)if(*buf=='-')sgn=-1;
    while(*buf>='0'&&*buf<='9'){a=a*10+(*buf-'0');buf++;}
    a*=sgn;
}

//char strtr[300100];
char aaa[300100], bbb[300100];
int tot;
void scanString(char *s){
    tot=0;
    for(;(*buf<'A'||*buf>'Z');buf++);
    while(*buf>='A'&&*buf<='Z'){s[tot++]=*buf;buf++;}
}
signed main(){
    fread(Buf,1,BUFSIZE,stdin); 
    //fastIO();
    scan(K); scan(N);
    //cin >> K >> N;
    for (int i = 1; i <= N; i++){
        string ca, cb;
        int a, b;
        scanString(aaa); scan(a); scanString(bbb); scan(b);
        //cin >> ca >> a >> cb >> b;
        if (aaa[0] == bbb[0]){
            same += abs(b-a);
        } else {
            if (aaa[0] == 'A'){
                A[++cnt] = a;
                B[cnt] = b;
            } else {
                A[++cnt] = b;
                B[cnt] = a;
            }
        }
    }
    if (K == 1){
        cout << solve1() << "\n";
    } else {
        solve2();
    }
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:204:10: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |     fread(Buf,1,BUFSIZE,stdin);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~

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