제출 #1054457

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1054457		Mokocraft	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	1 ms	356 KiB

bridge

#include <iostream>
#include <stdio.h>
#include <array>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>

bool sortByMiddle(std::pair<int, int>& a, std::pair<int, int>& b)
{
    return ((a.first + a.second) < (b.first + b.second));
}

int main()
{
    //freopen("duotaA.txt", "r", stdin);

    int K, N;
    std::cin >> K >> N;

    int extra = 0;
    std::vector<std::pair<int, int>> ranges;
    for(int i = 0; i < N; i++)
    {
        int ai, bi;
        char ac, bc;
        std::cin >> ac >> ai >> bc >> bi;

        if(ai > bi)
            std::swap(ai, bi);

        if(ac == bc)
            extra += bi - ai;
        else
            ranges.push_back(std::make_pair(ai, bi));
    }


    N = ranges.size();

    if(N == 0)
    {
        std::cout << extra;
        return 0;
    }

    if(K == 1)
    {
        long long dist = 0;
        int nums[N*2];
        for(int i = 0; i < N; i++)
        {
            nums[i*2] = ranges[i].first;
            nums[i*2+1] = ranges[i].second;
        }

        std::sort(nums, nums + N*2);

        int point = nums[N];

        for(int i = 0; i < N; i++)
        {
            if(point >= ranges[i].first && point <= ranges[i].second)
                dist += 1 + ranges[i].second - ranges[i].first;
            else dist += 1 + ranges[i].second - ranges[i].first + 2 * std::min(std::abs(ranges[i].second - point), std::abs(ranges[i].first - point));
        }

        std::cout << dist + extra;
    }
    else
    {
        std::sort(ranges.begin(), ranges.end(), sortByMiddle);

        int sumsFromRight[N+1];
        sumsFromRight[0] = 0;
        std::priority_queue<int> qL;
        int sumQl = 0;
        std::priority_queue<int, std::vector<int>, std::greater<int>> qR;
        int sumQr = 0;

        for(int i = N; i > 0; i--)
        {
            if(i == N)
            {
                qL.emplace(ranges[i-1].first);
                sumQl = qL.top();
                qR.emplace(ranges[i-1].second);
                sumQr = qR.top();
            }
            else
            {
                if(ranges[i-1].second <= qL.top())
                {
                    sumQl -= qL.top();
                    qR.emplace(qL.top());
                    sumQr += qL.top();
                    qL.pop();
                    sumQl += ranges[i-1].first + ranges[i-1].second;
                    qL.emplace(ranges[i-1].first);
                    qL.emplace(ranges[i-1].second);
                }
                else if(ranges[i-1].first >= qR.top())
                {
                    sumQr -= qR.top();
                    qL.emplace(qR.top());
                    sumQl += qR.top();
                    qR.pop();
                    sumQr += ranges[i-1].first + ranges[i-1].second;
                    qR.emplace(ranges[i-1].first);
                    qR.emplace(ranges[i-1].second);
                }
                else
                {
                    sumQl += ranges[i-1].first;
                    qL.emplace(ranges[i-1].first);
                    sumQr += ranges[i-1].second;
                    qR.emplace(ranges[i-1].second);
                }
            }
            sumsFromRight[N - i + 1] = sumQr - sumQl;
        }

        qL = std::priority_queue<int>();
        qR = std::priority_queue<int, std::vector<int>, std::greater<int>>();
        sumQl = 0;
        sumQr = 0;

        int dist = sumsFromRight[N];

        for(int i = 0; i < N; i++)
        {
            if(i == 0)
            {
                qL.emplace(ranges[i].first);
                sumQl = qL.top();
                qR.emplace(ranges[i].second);
                sumQr = qR.top();
            }
            else
            {
                if(ranges[i].second <= qL.top())
                {
                    sumQl -= qL.top();
                    qR.emplace(qL.top());
                    sumQr += qL.top();
                    qL.pop();
                    sumQl += ranges[i].first + ranges[i].second;
                    qL.emplace(ranges[i].first);
                    qL.emplace(ranges[i].second);
                }
                else if(ranges[i].first >= qR.top())
                {
                    sumQr -= qR.top();
                    qL.emplace(qR.top());
                    sumQl += qR.top();
                    qR.pop();
                    sumQr += ranges[i].first + ranges[i].second;
                    qR.emplace(ranges[i].first);
                    qR.emplace(ranges[i].second);
                }
                else
                {
                    sumQl += ranges[i].first;
                    qL.emplace(ranges[i].first);
                    sumQr += ranges[i].second;
                    qR.emplace(ranges[i].second);
                }
            }
            dist = std::min(dist, sumQr - sumQl + sumsFromRight[N-i-1]);
        }

        std::cout << dist + extra + N;
    }

    return 0;
}

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