Submission #1321892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321892		NValchanov	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	141 ms	13144 KiB

bridge

#include<bits/stdc++.h>
using namespace std;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

typedef long long llong;

const int MAXN = 1e5 + 10;
const int INF = 1e9 + 10;

struct Person
{
    int s, t;

    Person(){};

    Person(int s, int t)
    {
        this->s = s;
        this->t = t;
    }

    friend bool operator<(const Person &p1, const Person &p2)
    {
        return (p1.s + p1.t) < (p2.s + p2.t);
    }
};

llong same;
vector < Person > v;
int n, k;
char p[MAXN];
int s[MAXN];
char q[MAXN];
int t[MAXN];
multiset < int > lhalf, rhalf;

llong pref[MAXN];
llong suff[MAXN];
llong lhalfsum;
llong rhalfsum;

void read()
{
    cin >> k >> n;

    for(int i = 1; i <= n; i++)
    {
        cin >> p[i] >> s[i] >> q[i] >> t[i];

        if(p[i] == q[i])
        {
            same += abs(t[i] - s[i]);
        }
        else
        {
            v.push_back(Person(s[i], t[i]));
        }
    }

    sort(v.begin(), v.end());

    n = v.size();
}

void add(int val)
{
    int median;

    if(lhalf.empty())
        median = INF;
    else
        median = *lhalf.rbegin();

    if(val <= median)
    {
        lhalf.insert(val);
        lhalfsum += val;
    }
    else
    {
        rhalf.insert(val);
        rhalfsum += val;
    }

    if((int)rhalf.size() - (int)lhalf.size() > 1)
    {
        auto it = rhalf.begin();
        int trans = *it;

        rhalf.erase(it);
        rhalfsum -= trans;

        lhalf.insert(trans);
        lhalfsum += trans;
    }
    else if((int)lhalf.size() - (int)rhalf.size() > 1)
    {
        auto it = prev(lhalf.end());
        int trans = *it;

        lhalf.erase(it);
        lhalfsum -= trans;

        rhalf.insert(trans);
        rhalfsum += trans;
    }
}

void find_pref()
{
    lhalf.clear();
    rhalf.clear();

    lhalfsum = rhalfsum = 0;

    for(int i = 1; i <= n; i++)
    {
        add(v[i - 1].s);
        add(v[i - 1].t);

        pref[i] = rhalfsum - lhalfsum;
    }
}

void find_suff()
{
    lhalf.clear();
    rhalf.clear();

    lhalfsum = rhalfsum = 0;

    for(int i = n; i >= 1; i--)
    {
        add(v[i - 1].s);
        add(v[i - 1].t);

        suff[i] = rhalfsum - lhalfsum;
    }
}

void solve_k1()
{
    cout << (same + pref[n] + n) << endl;
}

void solve_k2()
{
    llong ans = pref[n];

    for(int i = 1; i <= n; i++)
    {
        ans = min(ans, pref[i] + suff[i + 1]);
    }

    cout << (same + ans + n) << endl;
}

void solve()
{
    if(k == 1)
        solve_k1();
    else
        solve_k2();
}

int main()
{
    speed();
    read();
    find_pref();
    find_suff();
    solve();

	return 0;
}
/**

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

*/

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