Submission #1052239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052239		kaopj	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	3 ms	3676 KiB

bridge

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
#define int long long
#define lgm cin.tie(0)->sync_with_stdio(0);
#define be(x) x.begin(),x.end()
#define v vector
#define f first
#define s second
const int mod = 1e9+7;
v<int> fac(200005,1);
int fp(int b,int r) {
    if (r==0) {
        return 1;
    } else if (r==1) {
        return b;
    }
    int a=fp(b,r/2);
    return a*a%mod*((r%2)?b:1)%mod;
}
int ncr(int n,int r) {
    if (n<r) {
        return 0;
    }
    return (fac[n]*fp(fac[n-r]*fac[r]%mod,mod-2))%mod;
}
int sqrt(int n) {
    int l=0,r=1e9,m;
    while (l<r) {
        m=(l+r)>>1;
        if (m*m>=n) {
            r=m;
        } else {
            l=m+1;
        }
    }
    return l;
}
multiset<int> a1,a2,b1,b2;
signed main() {
    for (int i=1;i<=200000;i++) {
        fac[i]=fac[i-1]*i%mod;
    }
    int k,n;
    cin >> k>>n;
    int r=0;
    v<pair<int,int>> p;
    int x,y;
    char z,w;
    for (int i=0;i<n;i++) {
        cin >> z>>x>>w>>y;
        if (z==w) {
            r+=abs(x-y);
        } else {
            if (x<y) {
                y^=x;
                x^=y;
                y^=x;
            }
            p.push_back({x,y});
        }
    }
    sort(be(p));
    if (k==1) {
        int sum1=0,sum2=0;
        for (auto [p1,p2]:p) {
            int a[2]={p1,p2};
            for (int i=0;i<2;i++) {
                if (a1.empty()) {
                    sum1+=a[i];
                    a1.insert(a[i]);
                } else {
                    if (a[i] > *a1.rbegin()) {
                        sum2+=a[i];
                        a2.insert(a[i]);
                        if (a2.size()>a1.size()) {
                            int f=*a2.begin();
                            sum2-=f;
                            sum1+=f;
                            a1.insert(f);
                            a2.erase(f);
                        }
                    } else {
                        sum1+=a[i];
                        a1.insert(a[i]);
                        if (!a2.empty() && a1.size()-a2.size()>(a1.size()+a2.size())%2) {
                            int f=*a1.rbegin();
                            sum2+=f;
                            sum1-=f;
                            a2.insert(f);
                            a1.erase(f);
                        }
                    }
                }
            }
        }
        cout << r+sum2-sum1+((n%2)?*a1.rbegin():0);
        return 0;
    }
    /*n=p.size();
    int sum00=0,sum10=0,sum01=0,sum11=0;
    for (auto [p1,p2]:p) {
        if (b1.empty()) {
            sum10+=p1;
            b1.insert(p1);
        } else {
            if (p1 > *b1.rbegin()) {
                sum11==p1;
                b2.insert(p1);
                if (b2.size()>b1.size()) {
                    int f=*b2.begin();
                    sum10+=f;
                    sum11-=f;
                    b1.insert(f);
                    b2.erase(f);
                }
            } else {
                b1.insert(p1);
                if (b1.size()-b2.size()>(b1.size()+b2.size())%2) {
                    int f=*b1.rbegin();
                    sum10-=f;
                    sum11+=f;
                    b2.insert(f);
                    b1.erase(f);
                }
            }
        }
        if (b1.empty()) {
            b1.insert(p2);
        } else {
            if (p2 > *b1.rbegin()) {
                b2.insert(p2);
                if (b2.size()>b1.size()) {
                    int f=*b2.begin();
                    sum10+=f;
                    sum11-=f;
                    b1.insert(f);
                    b2.erase(f);
                }
            } else {
                b1.insert(p2);
                if (b1.size()-b2.size()>(b1.size()+b2.size())%2) {
                    int f=*b1.rbegin();
                    sum10-=f;
                    sum11+=f;
                    b2.insert(f);
                    b1.erase(f);
                }
            }
        }
    }
    for (auto [p1,p2]:p) {

    }*/
}

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