Submission #1170131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170131		ASN49K	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	155 ms	11404 KiB

bridge

#include <bits/stdc++.h>

using i64 = long long;
#define all(x) x.begin(),x.end()
struct my_set
{
    i64  sum;
    std::multiset<int>mp;
    void insert(int x)
    {
        sum+=x;
        mp.insert(x);
    }
    void erase(int x)
    {
        sum-=x;
        mp.erase(mp.find(x));
    }
    int biggest()
    {
        return *mp.rbegin();
    }
    int smallest()
    {
        return *mp.begin();
    }
    void clear()
    {
        mp.clear();
        sum=0;
    }
};

my_set l,r;
void insert(int x,int y)
{
    l.insert(std::min(x,y));
    r.insert(std::max(x,y));

    int from_l=l.biggest();
    int from_r=r.smallest();
    if(from_l>from_r)
    {
        l.erase(from_l);
        r.erase(from_r);

        l.insert(from_r);
        r.insert(from_l);
    }

    assert(l.biggest()<=r.smallest());
}
i64 query()
{
    return r.sum-l.sum;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int cer,n;
    std::cin>>cer>>n;

    std::vector<std::pair<int,int>>a;

    i64 same_side=0,diff_side=0;
    for(int i=0;i<n;i++)
    {
        int x,y;
        char aa,b;
        std::cin>>aa>>x>>b>>y;
        if(aa==b)
        {
            same_side+=abs(y-x);
        }
        else
        {
            a.push_back({std::min(x,y) , std::max(x,y)});
        }
    }

    int sz=int(a.size());
    std::sort(all(a) , [&](std::pair<int,int>l,std::pair<int,int>r){
       return l.first+l.second<r.first+r.second;
    });

    for(auto &c:a)
    {
        //std::cout<<c.first<<' '<<c.second<<'\n';
    }
    std::vector<i64>prefix(sz+1,0);
    for(int i=0;i<sz;i++)
    {
        insert(a[i].first , a[i].second);
        prefix[i+1]=query();
    }


    l.clear();
    r.clear();
    diff_side=prefix[sz];

    if(cer==2)
    {
        for(int i=sz-1;i>=0;i--)
        {
            insert(a[i].first , a[i].second);
            diff_side=std::min(diff_side , query()+prefix[i]);
        }
    }
    //std::cout<<'\n'<<same_side<<' ';
    std::cout<<same_side + diff_side + sz;
}
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/



/*
2 5
 B 0 A 4
 B 1 B 3
 A 5 B 7
 B 2 A 6
 B 1 A 7


same_diff=2

nesortate
[0,4]
[5,7]
[2,6]
[1,7]


toate punctele

[0,1,2,4,5,6,7,7]

0,1,2,4,
5,6,7,7

25-7+2
*/

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