oj.uz

Submission #1054457

# Submission time Handle Problem Language Result Execution time Memory
1054457 2024-08-12T10:01:42 Z Mokocraft Palembang Bridges (APIO15_bridge) C++14
0 / 100
 1 ms 356 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 356 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -